#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e6;
 
int main()
{
    int cases;
    scanf("%d", &cases);
    
    while (cases--) {
    	int n;
    	scanf ("%d", &n);
    	
    	vector <int> cnt(n + 1);
    	for (int i = 0; i < n; i++) {
    		int d;
    		scanf("%d", &d);
    		if (d < n) {
        		cnt[d]++;
    		} else {
    		    cnt[n] = N;
    		}
    	}
    	
    	bool good = true;
    	for (int i = 1; i <= n; i++) if (cnt[i] > cnt[i-1]) {
    	    good = false;
    	    break;
    	}
    	
    	puts(good ? "YES" : "NO");
    }
}

#include "bits/stdc++.h"
using namespace std;
 
int main()
{
	int t;
	scanf ("%d", &t);
	while (t--) {
		long long n, k, g;
		scanf ("%lld %lld %lld", &n, &k, &g);
 
		long long stolen = min((g - 1) / 2 * n, k * g);
		long long rest = (k * g - stolen) % g;
 
		if (rest > 0) {
		    stolen -= (g - 1) / 2;
		    long long last = ((g - 1) / 2 + rest) % g;
 
		    if (last * 2 < g) {
		        stolen += last;
		    } else {
		        stolen -= g - last;
		    }
		}
 
		printf ("%lld\n", stolen);
	}
}

#include <bits/stdc++.h>

int power(int a, int e) {
    if (e == 0) return 1;
    return e == 1 ? a : a * power(a, e-1);
}

void answer(int a, int b) {
    std::cout << a << " + " << b << " = " << a+b << std::endl;
}

int main() {
    using ll = long long;
    
    int t;
    std::cin >> t;
    while (t--) {

        int a, b, c;
        ll k;
        std::cin >> a >> b >> c >> k;
        
        bool good = false;
    
        for (int i = power(10, a-1); i < power(10, a); ++i) {
            int left = std::max(power(10, b-1), power(10, c-1) - i);
            int right = std::min(power(10, b)-1, power(10, c) - 1 - i);
            if (left > right) continue;
    
            int have = right - left + 1;
            if (k <= have) {
                answer(i, left + k - 1);
                good = true;
                break;
            }
    
            k -= have;
        }
    
        if (!good) std::cout << "-1" << std::endl;
    }

    return 0;
}

#include <bits/stdc++.h>
 
#define forr(i, n) for (int i = 0; i < n; i++)
#define FOREACH(iter, coll) for (auto iter = coll.begin(); iter != coll.end(); ++iter)
#define FOREACHR(iter, coll) for (auto iter = coll.rbegin(); iter != coll.rend(); ++iter)
#define lbound(P, K, FUN) ({auto SSS=P, PPP = P-1, KKK=(K)+1; while(PPP+1!=KKK) {SSS = (PPP+(KKK-PPP)/2); if(FUN(SSS)) KKK = SSS; else PPP = SSS;} PPP; })
#define testy()    \
    int _tests;    \
    cin >> _tests; \
    FOR(_test, 1, _tests)
#define CLEAR(tab) memset(tab, 0, sizeof(tab))
#define CONTAIN(el, coll) (coll.find(el) != coll.end())
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
#define MP make_pair
#define PB push_back
#define ff first
#define ss second
#define deb(X) X;
#define SIZE(coll) ((int)coll.size())
 
#define M 1000000007
#define INF 1000000007LL
 
using namespace std;
 
long long n, m, k;
long long poz_l, poz_p;
vector<long long> v;
 
long long policz_ile(long long strzal)
{
    while (poz_l < n && v[poz_l] < strzal)
        poz_l++;
    while (poz_p < n && v[poz_p] <= strzal)
        poz_p++;
 
    long long pocz = poz_p < k ? 0 : (strzal + v[poz_p - k]) / 2 + 1;
    long long kon = poz_l + k - 1 >= n ? m : (v[poz_l + k - 1] + strzal - 1) / 2;
 
    return max(0ll, kon - pocz + 1);
}
 
int solve()
{
    cin >> n >> m >> k;
    long long a;
    forr(i, n)
    {
        cin >> a;
        v.PB(a);
    }
    sort(v.begin(), v.end());
    v.PB(m + 1);
    long long res = policz_ile(0), best = 0;
    forr(i, n)
    {
        long long pocz = i == 0 ? max(0ll, v[i] - 2) : max(v[i] - 2, v[i - 1] + 3);
        long long kon = min(m, v[i] + 2);
        for (long long s = pocz; s <= kon; s++)
        {
            long long ile = policz_ile(s);
 
            if (ile > res)
            {
                res = ile;
                best = s;
            }
        }
    }
    cout << res << " " << best << '\n';
 
    return 0;
}
 
int main()
{
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    solve();
 
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int k, n;
    scanf("%d", &k);

    n = 2 << k;

    vector <long long> input(n + 1);
    vector <int> memHighBits(1 << k, -1);
    vector <pair <int, int> > memLowBits(1 << k, {-1, -1});
    
    auto addInterval = [&memLowBits, &input](int s, int e) {
        const int remXor = input[e] ^ input[s - 1];
        auto &[os, oe] = memLowBits[remXor];

        if (os == -1) {
            os = s, oe = e;
            return false;
        }

        if (oe < s) {
            printf("%d %d %d %d\n", os, oe, s, e);
        } else {
            printf("%d %d %d %d\n", min(s, os), max(s, os) - 1, oe + 1, e);
        }

        return true;
    };

    memHighBits[0] = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &input[i]);
        input[i] ^= input[i - 1];
    }

    for (int i = 1; i <= n; ++i) {
        if (memHighBits[input[i] >> k] != -1) {
            if (addInterval(memHighBits[input[i] >> k] + 1, i)) {
                break;
            }
        }

        memHighBits[input[i] >> k] = i;
    }
}

int main()
{
    int cases;
    scanf("%d", &cases);

    while (cases--) {
        solve();
    }

    return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define pb push_back
#define FOR(i, n) for(int i = 0; i < n; i++)
 
using vi = vector<int>;
using vvi = vector<vi>;
 
struct SCC {
    int cnt = 0;
    vi vis, scc_nr;
    vvi scc_list, DAG;
 
    SCC(){}
 
    SCC(vvi & G){
        // G is 0 indexed!
        int n = sz(G);
        vvi G_rev(n);
        vis = scc_nr = vi(n);
 
        vi postorder;
        for(int i = 0; i < n; i++)
            if(!vis[i])
                dfs_post(i, G, G_rev, postorder);
        
        vis = vi(n);
        while(sz(postorder)){
            auto akt = postorder.back();
            postorder.pop_back();
            if(!vis[akt]){
                DAG.emplace_back();
                scc_list.emplace_back();
                dfs_rev(akt, G_rev);
                cnt++;
            }
        }
 
        // optional
        for(int i = 0; i < sz(DAG); i++){
            sort(all(DAG[i]));
            DAG[i].resize(unique(all(DAG[i])) - DAG[i].begin());
        }
    }
 
    void dfs_post(int start, vvi & G, vvi & G_rev, vi & postorder){
        vis[start] = 1;
        for(auto & u : G[start]){
            G_rev[u].pb(start);
            if(!vis[u])
                dfs_post(u, G, G_rev, postorder);
        }
        
        postorder.pb(start);
    }
 
    void dfs_rev(int start, vvi & G_rev){
        vis[start] = true;
        scc_list.back().pb(start);
        scc_nr[start] = cnt;
 
        for(auto & u : G_rev[start])
            if(!vis[u])
                dfs_rev(u, G_rev);
            else if(scc_nr[u] != cnt)
                DAG[scc_nr[u]].pb(cnt);
    }
};
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    long long n, m, k;
    cin >> n >> m >> k;
 
    vvi G(n);
 
    set<pair<int, int>> edges;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        G[a].pb(b);
        edges.insert({a, b});
    }
 
    SCC scc(G);
    vi coloring(n, -1);
 
    auto try_coloring = [&](int num_col, const vi& group)
    {
        vi visited;
        function<bool(int)> dfs = [&](int start){
            visited.pb(start);
            
            bool good_coloring = true;
            for (auto & u : G[start])
            {
                if (scc.scc_nr[u] != scc.scc_nr[start])
                {
                    continue;
                }
                if (coloring[u] == -1)
                {
                    coloring[u] = (coloring[start] + 1) % num_col;
                    good_coloring &= dfs(u);
                }
                else
                {
                    good_coloring &= coloring[u] == (coloring[start] + 1) % num_col;
                }
 
                if (not good_coloring)
                {
                    break;    
                }
            }
 
            return good_coloring;
        };
 
        coloring[group[0]] = 0;
        if (not dfs(group[0]))
        {
            for (auto & u : visited)
            {
                coloring[u] = -1;
            }
            return vvi();
        }
        else
        {
            vvi ret(num_col);
            for (auto & u : visited)
            {
                ret[coloring[u]].push_back(u);
            }
            return ret;
        }
    };
 
    long long ans = 0;
    vi depths(n, -1);
 
    for (vi& group : scc.scc_list)
    {
        n = sz(group);
 
        if (n == 1 and edges.count({group[0], group[0]}) == 0)
        {
            continue;
        }
        int gcd = -1;
        function<void(int)> dfs_depths = [&](int start)
        {
            for (auto & u : G[start])
            {
                if (scc.scc_nr[u] != scc.scc_nr[start])
                {
                    continue;
                }
 
                if (depths[u] == -1)
                {
                    depths[u] = depths[start] + 1;
                    dfs_depths(u);
                }
                else {
                    int diff = abs(depths[u] - (depths[start] + 1));
                    if (diff)
                    {
                        if (gcd == -1)
                        {
                            gcd = diff;
                        }
                        else
                        {
                            gcd = __gcd(gcd, diff);
                        }
                    }
                }
            }
        };
 
        depths[group[0]] = 0;
        dfs_depths(group[0]);
        assert(gcd != -1);
 
        vvi by_color = try_coloring(gcd, group);
 
        assert(sz(by_color) != 0);
        if (k % gcd == 0)
        {
            FOR (i, gcd)
            {
                ans += sz(by_color[i]) + 1ll * sz(by_color[i]) * (sz(by_color[i]) - 1) / 2;
            }
        }
        else if (k % gcd * 2 == gcd)
        {
            FOR (i, gcd / 2)
            {
                ans += 1ll * sz(by_color[i]) * sz(by_color[i + gcd / 2]);
            }
        }
    }
    cout << ans << '\n';
}

#include <bits/stdc++.h>
 
using namespace std;
 
constexpr int MAX_M = 1000 + 7;
constexpr int PRECISION = 9;
constexpr long long MOD = 1e9 + 7;
 
long long mod_inv[MAX_M];
long long DP[MAX_M][MAX_M][2][2];
long long DPprob[MAX_M][MAX_M][2][2];
bool updated[MAX_M][MAX_M][2][2];
// DP[correct][incorrect][backspace][bad suffix]
 
long long calc_mod_inv(long long n)
{
    long long res = 1;
    long long exp = MOD - 2;
 
    while (exp)
    {
        if (exp & 1)
        {
            res = (res * n) % MOD;
        }
 
        exp >>= 1;
        n = (n * n) % MOD;
    }
 
    return res;
}
 
void calc_DP(int digits, int needed)
{
    DP[0][0][0][0] = 0;
    DPprob[0][0][0][0] = 1;
 
    struct ID
    {
        int x, y, z, s;
    };
 
    queue <ID> dp_queue;
    dp_queue.push({0, 0, 0, 0});
 
    while(!dp_queue.empty())
    {
        auto [x, y, z, s] = dp_queue.front();
        dp_queue.pop();
 
        if (updated[x][y][z][s])
        {
            continue;
        }
 
        updated[x][y][z][s] = true;
 
        long long left = digits + 1 - x - y - z;
        long long corr = needed - x;
        long long incorr = digits - needed - y;
        long long prob = DPprob[x][y][z][s];
 
        if (corr == 0 and s == 0)
        {
            // done
            continue;
        }
 
        // correct suffix
        if (s == 0)
        {
            if (corr > 0)
            {
                // found the one correct digit (no need to delete)
                long long opt_prob = (prob * mod_inv[left]) % MOD;
                DPprob[x + 1][y][z][0] = (DPprob[x + 1][y][z][0] + opt_prob) % MOD;
                DP[x + 1][y][z][0] = (DP[x + 1][y][z][0] + DP[x][y][z][0] * mod_inv[left]) % MOD;
 
                // found a needed but currently wrong digit (needs to be deleted)
                if (corr > 1)
                {
                    if (z == 0) // if backspace is not known, the suffix is bad
                    {
                        long long opt_prob = ((prob * (corr - 1) % MOD) * mod_inv[left]) % MOD;
                        DPprob[x + 1][y][z][1] = (DPprob[x + 1][y][z][1] + opt_prob) % MOD;
 
                        DP[x + 1][y][z][1] = (DP[x + 1][y][z][1] + ((corr - 1) * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD;
                        dp_queue.push({x + 1, y, z, 1});
                    }
                    else // if backspace is known, the suffix can be instantly repaired
                    {
                        long long opt_prob = ((prob * (corr - 1) % MOD) * mod_inv[left]) % MOD;
                        DPprob[x + 1][y][z][0] = (DPprob[x + 1][y][z][0] + opt_prob) % MOD;
                        DP[x + 1][y][z][0] = (DP[x + 1][y][z][0] + ((corr - 1) * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD;
                    }
                }
 
                dp_queue.push({x + 1, y, z, 0});
            }
 
            if (incorr > 0)
            {
                // found an incorrect digit
                if (z == 0)
                {
                    long long opt_prob = (prob * incorr % MOD) * mod_inv[left] % MOD;
                    DPprob[x][y + 1][z][1] = (DPprob[x][y + 1][z][1] + opt_prob) % MOD;
                    DP[x][y + 1][z][1] = (DP[x][y + 1][z][1] + (incorr * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD;
                    dp_queue.push({x, y + 1, z, 1});
                }
                else // suffix can be repaired
                {
                    long long opt_prob = ((prob * incorr % MOD) * mod_inv[left]) % MOD;
                    DPprob[x][y + 1][z][0] = (DPprob[x][y + 1][z][0] + opt_prob) % MOD;
                    DP[x][y + 1][z][0] = (DP[x][y + 1][z][0] + (incorr * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD;
                    dp_queue.push({x, y + 1, z, 0});
                }
            }
 
            if (z == 0)
            {
                if (x > 0) // deleted correct digit
                {
                    long long opt_prob = prob * mod_inv[left] % MOD;
                    DPprob[x][y][1][0] = (DPprob[x][y][1][0] + opt_prob) % MOD;
                    DP[x][y][1][0] = (DP[x][y][1][0] + mod_inv[left] * DP[x][y][0][0] + 2 * opt_prob) % MOD;
                }
                else // deleted nothing
                {
                    long long opt_prob = prob * mod_inv[left] % MOD;
                    DPprob[x][y][1][0] = (DPprob[x][y][1][0] + opt_prob) % MOD;
                    DP[x][y][1][0] = (DP[x][y][1][0] + mod_inv[left] * DP[x][y][0][0] + opt_prob) % MOD;
                }
 
                dp_queue.push({x, y, 1, 0});
            }
        }
 
        if (s == 1)
        {
            if (corr > 0)
            {
                // found a needed but currently wrong digit (needs to be deleted)
                long long opt_prob = (prob * corr % MOD) * mod_inv[left] % MOD;
                DPprob[x + 1][y][z][1] = (DPprob[x + 1][y][z][1] + opt_prob) % MOD;
                DP[x + 1][y][z][1] = (DP[x + 1][y][z][1] + (corr * mod_inv[left] % MOD) * DP[x][y][z][1] + 2 * opt_prob) % MOD;
                dp_queue.push({x + 1, y, z, 1});
            }
 
            if (incorr > 0)
            {
                // found an incorrect digit
                long long opt_prob = (prob * incorr % MOD) * mod_inv[left] % MOD;
                DPprob[x][y + 1][z][1] = (DPprob[x][y + 1][z][1] + opt_prob) % MOD;
                DP[x][y + 1][z][1] = (DP[x][y + 1][z][1] + (incorr * mod_inv[left] % MOD) * DP[x][y][z][1] + 2 * opt_prob) % MOD;
                dp_queue.push({x, y + 1, z, 1});
            }
 
            if (z == 0)
            {
                // deleted bad suffix
                long long opt_prob = prob * mod_inv[left] % MOD;
                DPprob[x][y][1][0] = (DPprob[x][y][1][0] + opt_prob) % MOD;
                DP[x][y][1][0] = (DP[x][y][1][0] + mod_inv[left] * DP[x][y][0][1]) % MOD;
                dp_queue.push({x, y, 1, 0});
            }
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    mod_inv[0] = 1;
    for (int i = 1; i < MAX_M; ++i) {
        mod_inv[i] = calc_mod_inv(i);
        assert (mod_inv[i] * i % MOD == 1);
    }
 
    int n, m;
    cin >> n >> m;
 
    set <int> different_digits;
 
    for (int i = 0; i < n; ++i)
    {
        int p;
        cin >> p;
 
        different_digits.insert(p);
    }
 
    int needed = different_digits.size();
 
    calc_DP(m, needed);
 
    long long result = 0;
 
    for (int i = 0; i <= MAX_M; ++i)
    {
        result = (result + DP[needed][i][0][0]) % MOD;
        result = (result + DP[needed][i][1][0]) % MOD;
    }
 
    cout << (result + n) % MOD << "\n";
 
    return 0;
}

#include <bits/stdc++.h>

#define forr(i, n) for (int i = 0; i < n; i++)
#define FOREACH(iter, coll) for (auto iter = coll.begin(); iter != coll.end(); ++iter)
#define FOREACHR(iter, coll) for (auto iter = coll.rbegin(); iter != coll.rend(); ++iter)
#define lbound(P, K, FUN) ({auto SSS=P, PPP = P-1, KKK=(K)+1; while(PPP+1!=KKK) {SSS = (PPP+(KKK-PPP)/2); if(FUN(SSS)) KKK = SSS; else PPP = SSS;} PPP; })
#define testy()    \
    int _tests;    \
    cin >> _tests; \
    FOR(_test, 1, _tests)
#define CLEAR(tab) memset(tab, 0, sizeof(tab))
#define CONTAIN(el, coll) (coll.find(el) != coll.end())
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
#define MP make_pair
#define PB push_back
#define ff first
#define ss second
#define deb(X) X;
#define SIZE(coll) ((int)coll.size())

using namespace std;

const int MXN = 1007;
int n, m;
vector<int> G[MXN];
bitset<MXN> bs[MXN], edge[MXN];

// MATCHING

const int MXM = 1007 * 2;
int skojX[MXM], skojY[MXM];
bool vis[MXM];

bool dfs_m(int x)
{
    vis[x] = 1;
    FOREACH(it, G[x])
    if (!skojY[*it] || (!vis[skojY[*it]] && dfs_m(skojY[*it])))
    {
        skojX[x] = *it;
        skojY[*it] = x;
        return 1;
    }
    return 0;
}

bool skoj()
{
    int czy = 1;
    int res = 0;
    while (czy)
    {
        czy = 0;
        CLEAR(vis);
        FOR(i, 1, n)
        if (!vis[i] && !skojX[i] && dfs_m(i))
        {
            czy = 1;
            res++;
        }
    }
    return res == n;
}

// END OF MATCHING

void dfs(int nr, bitset<MXN> &visited, bitset<MXN> &to_visit)
{
    visited[nr] = 1;
    to_visit[nr] = 0;
    to_visit = to_visit | (edge[nr] & (~visited));
    for (int i = to_visit._Find_first(); i < SIZE(to_visit); i = to_visit._Find_next(i))
        dfs(i, visited, to_visit);
}

int solve()
{
    cin >> n >> m;
    forr(i, m)
    {
        int a, b;
        cin >> a >> b;
        G[a].PB(b);
    }

    int rres = skoj();
    if (rres)
    {
        FOR(i, 1, n)
        {
            for (auto j : G[i])
            {
                edge[i][skojY[j]] = 1;
            }
        }
        unordered_map<bitset<MXN>, vector<int>> mapa;
        vector<pair<int, int>> vec, res;
        FOR(i, 1, n)
        {
            bitset<MXN> to_visit;
            dfs(i, bs[i], to_visit);
            mapa[bs[i]].PB(i);
        }

        for (auto p : mapa)
        {
            vector<int> l = p.ss;
            vec.PB({bs[l[0]].count(), l[0]});
            if (l.size() == 1)
            {
                res.PB({l[0], l[0]});
                continue;
            }
            for (int i = 0; i < SIZE(l); i++)
            {
                res.PB({l[i], l[i]});
                res.PB({l[i], l[(i + 1) % SIZE(l)]});
            }
        }
        sort(vec.begin(), vec.end());
        forr(i, SIZE(vec))
        {
            int nr = vec[i].ss;
            bitset<MXN> b;
            for (int j = i - 1; j >= 0; j--)
                if (vec[j].ff < vec[i].ff)
                {
                    int nr2 = vec[j].ss;
                    if (bs[nr][nr2] && !b[nr2])
                    {
                        b |= bs[nr2];
                        res.PB({nr, nr2});
                    }
                }
        }

        cout << "YES" << '\n';
        cout << res.size() << '\n';
        for (auto p : res)
            cout << p.ff << " " << p.ss + n << '\n';
    }
    else
    {
        CLEAR(vis);
        FOR(i, 1, n)
        {
            if (skojX[i] == 0)
            {
                dfs_m(i);
                break;
            }
        }
        vector<int> v;
        FOR(i, 1, n)
        {
            if (vis[i])
                v.PB(i);
        }
        cout << "NO" << '\n';
        cout << v.size() << '\n';
        for (auto el : v)
            cout << el << " ";
        cout << '\n';
    }

    return 0;
}

int main()
{
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	scanf("%d", &n);

	vector <int> in(n);
	vector <int> is(N);

	for(auto &p: in)
		scanf("%d", &p);
	
	for(int i = 0; i < n; ++i)
		for(int j = i + 1; j < n; ++j)
			is[in[j] - in[i]] = true;
	
	int ans = 0;
	for(auto &v: is)
		ans += v;
	printf("%d\n", ans);
}

int main() {
	int cases;
	scanf("%d", &cases);
	
	while(cases--)
		solve();
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	scanf("%d", &n);

	vector <int> in(n);
	for(auto &p: in)
		scanf("%d", &p);
	
	set <int> S;
	for(int i = 0; i < n; ++i)
		for(int j = i + 1; j < n; ++j)
			S.insert(in[j] - in[i]);

	printf("%d\n", (int)S.size());
}

int main() {
	int cases;
	scanf("%d", &cases);
	
	while(cases--)
		solve();
	return 0;
}

Try to solve it for $$$n, x_i \leq 10^5$$$.

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	scanf("%d", &n);
	
	int ans = 0;
	int prv = 0, ok = 0;
	
	for(int i = 1; i <= n; ++i) {
		int a;
		scanf("%d", &a);
		
		ans += (a != prv);
		ok |= (a == prv);
		
		if(prv + 1 < a)
			ans += ok, ok = 0;
		prv = a;
	}
	
	ans += ok;
	printf("%d\n", ans);
}

int main() {
	int cases;
	scanf("%d", &cases);
	
	while(cases--)
		solve();
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	scanf("%d", &n);

	set <int> S;
	for(int i = 1; i <= n; ++i) {
		int v;
		scanf("%d", &v);

		if(S.count(v))
			v++;
		S.insert(v);
	}
	
	printf("%d\n", (int)S.size());
}

int main() {
	int cases;
	scanf("%d", &cases);
	
	while(cases--)
		solve();
	return 0;
}

Can you solve it if we can increase note $$$x_i$$$ by any integer in $$$[0, k_i]$$$, for given $$$k_i$$$?

#include <bits/stdc++.h>

using namespace std;

const int N = 100 * 1000 + 7;

int n;
char in[N];
bool used[N];

void solve(){
	scanf("%s", in + 1);
	n = strlen(in + 1);
	
	for(int i = 1; i <= n; ++i)
		used[i] = false;
	
	int ans = 0;
	for(int i = 2; i <= n; ++i){
		bool use_need = false;
		if(in[i] == in[i - 1] && !used[i - 1])
			use_need = true;

		if(i > 2 && in[i] == in[i - 2] && !used[i - 2])
			use_need = true;

		used[i] = use_need;
		ans += used[i];
	}
	
	printf("%d\n", ans);
}

int main(){
	int cases;
	scanf("%d", &cases);
	
	while(cases--)
		solve();
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 7;

int n;
char in[N];
int dp[N][2][2];

void solve(){
	scanf("%s", in + 1);
	n = strlen(in + 1);

	for(int ta = 0; ta < 2; ++ta)
		for(int tb = 0; tb < 2; ++tb)
			dp[0][ta][tb] = 0;

	for(int i = 1; i <= n; ++i)
		for(int ta = 0; ta < 2; ++ta)
			for(int tb = 0; tb < 2; ++tb)
				dp[i][ta][tb] = N;
	
	for(int i = 1; i <= n; ++i){
		if(in[i] != in[i - 1]){
			if(in[i] != in[i - 2])
				dp[i][0][0] = min(dp[i][0][0], dp[i - 1][0][0]);
			dp[i][0][0] = min(dp[i][0][0], dp[i - 1][0][1]);
		}
		
		if(in[i] != in[i - 2])
			dp[i][0][1] = min(dp[i][0][1], dp[i - 1][1][0]);
		dp[i][0][1] = min(dp[i][0][1], dp[i - 1][1][1]);
		
		dp[i][1][0] = min(dp[i][1][0], min(dp[i - 1][0][0], dp[i - 1][0][1]) + 1);
		dp[i][1][1] = min(dp[i][1][1], min(dp[i - 1][1][0], dp[i - 1][1][1]) + 1);
	}
	
	int ans = N;
	for(int ta = 0; ta < 2; ++ta)
		for(int tb = 0; tb < 2; ++tb)
			ans = min(ans, dp[n][ta][tb]);
	printf("%d\n", ans);
}

int main(){
	int cases;
	scanf("%d", &cases);
	
	while(cases--)
		solve();
	return 0;
}

What if letters can change, and you need the calculate the result after each change?

#include <bits/stdc++.h>

using namespace std;

typedef long long int LL;

const int N = 100 * 1000 + 7;

int n;
int w[N];
int deg[N];

void solve() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &w[i]);
		deg[i] = 0;
	}
	
	for(int i = 1; i < n; ++i) {
		int u, v;
		scanf("%d %d", &u, &v);
		deg[u]++; deg[v]++;
	}
	
	LL ans = 0;
	vector <int> to_sort;

	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j < deg[i]; ++j)
			to_sort.push_back(w[i]);
		ans += w[i];
	}
	
	sort(to_sort.begin(), to_sort.end());
	reverse(to_sort.begin(), to_sort.end());
	
	for(auto &v: to_sort) {
		printf("%lld ", ans);
		ans += v;
	}
	
	printf("%lld\n", ans);
}

int main() {
	int cases;
	scanf("%d", &cases);
	
	while(cases--)
		solve();
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef long long int LL;

const int N = 500 * 1000 + 7;
const int P = 60;
const int MX = 1e9 + 7;

int n;
LL in[N];
int cnt[P];

void solve(){
	scanf("%d", &n);
	for(int i = 0; i < P; ++i)
		cnt[i] = 0;
	
	for(int i = 1; i <= n; ++i){
		scanf("%lld", &in[i]);
		for(int j = 0; j < P; ++j)
			cnt[j] += in[i] >> j & 1;
	}
	
	int ans = 0;
	for(int i = 1; i <= n; ++i){
		LL exp_or = 0, exp_and = 0;
		for(int j = 0; j < P; ++j){
			if(in[i] >> j & 1){
				exp_or += (1LL << j) % MX * n;
				exp_and += (1LL << j) % MX * cnt[j];
			}
			else
				exp_or += (1LL << j) % MX * cnt[j];
		}
		
		exp_and %= MX, exp_or %= MX;
		ans = (ans + 1LL * exp_or * exp_and) % MX;
	}
	
	printf("%d\n", ans);
}

int main(){
	int cases;
	scanf("%d", &cases);
	
	while(cases--)
		solve();
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef long long int LL;

const int N = 5e5 + 7;
const int MX = 1e9 + 7;

int n, m;
int rep[N];

int Find(int a) {
	if(rep[a] == a)
		return a;
	return rep[a] = Find(rep[a]);
}

bool Union(int a, int b) {
	a = Find(a);
	b = Find(b);
	
	rep[a] = b;
	return a != b;
}

int main() {
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m + 1; ++i)
		rep[i] = i;
	
	vector <int> ans;
	for(int i = 1; i <= n; ++i) {
		int k;
		scanf("%d", &k);
		
		int fa, fb = m + 1;
		scanf("%d", &fa);
		
		if(k > 1)
			scanf("%d", &fb);
		
		if(Union(fa, fb))
			ans.push_back(i);
	}
	
	int res = 1;
	for(int i = 0; i < (int)ans.size(); ++i)
		res = (res + res) % MX;

	printf("%d %d\n", res, (int)ans.size());
	for(auto v: ans)
		printf("%d ", v);
	puts("");
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int MAXLEN = 1e6 + 7;
const int MOD = 1e9 + 7;

int n, q;
string s, t;
vector <string> songs;

vector <int> pw;
vector <int> sum[26];

void read(string &p) {
	static char input[MAXLEN];
	scanf("%s", input);
	p = input;
}

void prepare_songs() {
	songs = {s};
	for(auto c: t) {
		if(songs.back().size() >= MAXLEN)
			break;
		
		auto p = songs.back();
		auto nxt = p + string(1, c) + p;
		songs.push_back(nxt);
	}
}

void prepare_sum() {
	for(int i = 0; i < 26; ++i) {
		char c = 'a' + i;
		sum[i].resize(n + 1, 0);
		
		for(int j = 0; j < n; ++j)
			sum[i][j + 1] = (sum[i][j] * 2 + (t[j] == c)) % MOD;
	}
	
	pw.resize(n + 1, 0);
	pw[0] = 1;
	
	for(int i = 1; i <= n; ++i)
		pw[i] = 2LL * pw[i - 1] % MOD;
}

void init() {
	scanf("%d %d", &n, &q);
	read(s), read(t);

	prepare_songs();
	prepare_sum();
}

vector <int> kmp(string &in) {
	int m = in.size(), cpref = 0;
	vector <int> dp(m, 0);
	
	for(int i = 1; i < (int)in.size(); ++i) {
		while(cpref > 0 && in[cpref] != in[i])
			cpref = dp[cpref - 1];
		
		if(in[cpref] == in[i])
			++cpref;
		dp[i] = cpref;
	}
	
	return dp;
}

/* Get all borders based on dp from kmp */
vector <bool> get(vector <int> &dp, int m) {
	vector <bool> ret(m + 1, false);
	int cur = dp.back();
	
	while(cur) {
		ret[cur] = true;
		cur = dp[cur - 1];
	}
	
	ret[cur] = true;
	return ret;
}

int answer(int k, string &w) {
	int id = 0;
	while(songs[id].size() < w.size())
		++id;
	
	if(id > k)
		return 0;
	
	int m = w.size();
	string s_pref = w + '#' + songs[id];
	string s_suf = songs[id] + '#' + w;
	
	auto dp_pref = kmp(s_pref);
	auto dp_suf = kmp(s_suf);
	
	auto pref = get(dp_pref, m);
	auto suf = get(dp_suf, m);
	
	/* Compute all internal occurences */
	int ret = 0;
	for(auto &v: dp_pref)
		ret += (v == m);
	ret = 1LL * ret * pw[k - id] % MOD;
	
	/* Compute the remaining occurences */
	for(int i = 0; i < m; ++i) {
		if(!pref[i] || !suf[m - i - 1])
			continue;
		
		int c = w[i] - 'a';
		ret = (ret + sum[c][k] - 1LL * sum[c][id] * pw[k - id]) % MOD;
	}
	
	ret = (ret + MOD) % MOD;
	return ret;
}

void solve() {
	while(q--) {
		int k;
		string w;
		
		scanf("%d", &k);
		read(w);
		printf("%d\n", answer(k, w));
	}
}

int main() {
	init();
	solve();
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef long long int LL;

#define st first
#define nd second
#define PII pair <int, int>

const int N = 60;
const int MX = 1e9 + 7;

struct state {
	int sum_picked = 0;
	int last_picked = 0, cur_picked = 0;
	int iterator = 0;
	vector <PII> lengths;
	
	state(vector <PII> _lengths) {
		lengths = _lengths;
	}
	
	/* operators for map comparisons */
	bool operator<(const state &s) const {
		if(lengths != s.lengths)			return lengths < s.lengths;
		if(last_picked != s.last_picked)	return last_picked < s.last_picked;
		if(cur_picked != s.cur_picked)		return cur_picked < s.cur_picked;
		return iterator < s.iterator;
	}
	
	bool operator==(const state &s) const {
		if(last_picked != s.last_picked)	return false;
		if(cur_picked != s.cur_picked)		return false;
		if(iterator != s.iterator)			return false;
		if(lengths != s.lengths)			return false;
		return true;
	}
};

int n;
vector <PII> cycles;
map <state, int> dp;

int sil[N], rv[N];
int pre[N][N][N];

int fast(int a, int b) {
	int ret = 1;
	while(b) {
		if(b & 1)
			ret = 1LL * ret * a % MX;
		
		b >>= 1;
		a = 1LL * a * a % MX;
	}
	
	return ret;
}

int newt(int a, int b) {
	if(b < 0 || a < b)
		return 0;
	return 1LL * sil[a] * rv[b] % MX * rv[a - b] % MX;
}

PII get_ways(int a, int b) {
	if(a == 0 && b == 0)
		return {sil[n - 1], 0};

	int ret = 0, ret2 = 0;
	int c = n - a - 1;
	
	for(int t = 1; t + c <= n; ++t) {
		ret = (ret + 1LL * newt(n - t, c) * sil[c] % MX * newt(n - c - 1, b) % MX * sil[b] % MX * sil[a - b]) % MX;
		ret2 = (ret2 + 1LL * newt(n - t, c) * sil[c] % MX * newt(n - t - c, b) % MX * sil[b] % MX * sil[a - b]) % MX;
	}

	return {ret, ret2};
}

void precalc() {
	sil[0] = 1;
	for(int i = 1; i <= n; ++i)
		sil[i] = 1LL * sil[i - 1] * i % MX;
	
	rv[n] = fast(sil[n], MX - 2);
	for(int i = n; i >= 1; --i)
		rv[i - 1] = 1LL * rv[i] * i % MX;
	
	for(int i = 0; i < n; ++i)
		for(int j = 0; j <= i; ++j) {
			if(i && j == 0)
				continue;
			
			auto [val, val2] = get_ways(i, j);
			pre[i][j][0] = 1;

			int res = 1, res2 = 1;
			for(int k = 1; k <= n; ++k) {
				res = 1LL * res * val % MX;
				res2 = 1LL * res2 * val2 % MX;
				pre[i][j][k] = (res + MX - res2) % MX;
			}
		}
}

void read() {
	scanf("%d", &n);
	precalc();

	vector <int> input(n);
	for(auto &v: input) {
		scanf("%d", &v);
		v--;
	}
	
	vector <bool> vis(n);
	vector <int> cycle_lengths;

	for(int i = 0; i < n; ++i) {
		if(vis[i])
			continue;
		
		int cur = i;
		int cycle_length = 0;
		
		while(!vis[cur]) {
			++cycle_length;
			vis[cur] = true;
			cur = input[cur];
		}
		
		cycle_lengths.push_back(cycle_length);
	}
	
	sort(cycle_lengths.begin(), cycle_lengths.end());
	for(auto v: cycle_lengths) {
		if(cycles.size() && cycles.back().st == v)
			cycles.back().nd++;
		else
			cycles.push_back({v, 1});
	}
}

int solve(state &cur) {
	if(cur.sum_picked == n)
		return 1;
	
	if(dp.count(cur))
		return dp[cur];
	
	if(cur.iterator == (int)cur.lengths.size()) {
		if(cur.cur_picked == 0)
			return dp[cur] = 0;
		
		state nxt = cur;
		nxt.sum_picked += nxt.cur_picked;
		nxt.last_picked = nxt.cur_picked;
		nxt.cur_picked = 0;
		nxt.iterator = 0;
		return dp[cur] = solve(nxt);
	}
	
	state nxt = cur;
	nxt.iterator++;
	
	int ret = 0, tmp = 1;
	auto [length, count] = cur.lengths[cur.iterator];

	for(int i = 0; i <= count; ++i) {
		nxt.cur_picked = cur.cur_picked + i * length;
		nxt.lengths[cur.iterator].nd = count - i;
		ret = (ret + 1LL * solve(nxt) * tmp % MX * newt(count, i)) % MX;
		tmp = 1LL * tmp * pre[cur.sum_picked][cur.last_picked][length] % MX;
	}
	
	return dp[cur] = ret;
}

int main() {
	read();
	state start = state(cycles);
	int ans = solve(start);
	printf("%d\n", ans);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define st first
#define nd second

int n, b;

void write(int i, string y){
	printf("%d ", i);
	for(auto p: y)
		printf("%c", p);
	puts("");
	fflush(stdout);
}

bool ask(int i, string y){
	write(i, y);
	string ans;
	cin >> ans;
	return ans == "yes";
}

void solve(vector <int> cur, string pref){
	if(pref.size() == b){
		write(0, pref);
		return;
	}

	stack <pair <int, string> > S;
	S.push({0, pref});
	
	for(auto v: cur){
		while(S.size() > 1){
			auto prv = S.top().nd;
			while(prv.size() < b)
				prv.push_back('1');

			if(!ask(v, prv))
				break;
			S.pop();
		}
		
		if(S.top().nd.size() == b)
			continue;
		
		auto prv = S.top().nd;
		prv.push_back('0');

		while(prv.size() < b)
			prv.push_back('1');

		if(ask(v, prv)){
			prv = S.top().nd + "1";
			S.push({v, prv});
		}
		else{
			prv = S.top().nd + "0";
			S.push({v, prv});
		}
	}
	
	vector <int> nxt;
	string ans = S.top().nd;
	
	while(S.size() > 1){
		auto p = S.top();
		S.pop();
		
		string tmp = ans;
		while(tmp.size() < b)
			tmp.push_back('1');
		
		if(ask(p.st, tmp)){
			nxt.clear();
			ans = p.nd;
		}
		
		nxt.push_back(p.st);
	}
	
	solve(nxt, ans);
}

int main(){
	scanf("%d %d", &n, &b);
	vector <int> all_ids;
	for(int i = 0; i < n; ++i)
		all_ids.push_back(i + 1);
	solve(all_ids, "");
	return 0;
}

We can observe that result cannot exceed 201 — Awruk gets at least 101 votes from one person and Elodreip cannot get more than 100 votes from one person. So we can iterate over every possible integer from 1 to 201 and check if Awruk wins with k set to this integer. We have to remember that k — a_i is always at least 0, so we have to check this condition too. Complexity O(n * M), where M denotes maximum possible value of a_i. Try to solve it in O(n).

#include <bits/stdc++.h>

using namespace std;

int n;
int mx = 0, sum = 0;

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i){
		int a;	scanf("%d", &a);
		mx = max(mx, a);
		sum += a;
	}
	
	sum *= 2;
	sum += n;
	sum /= n;
	
	printf("%d", max(sum, mx));
	return 0;
}

First, let's observe that we can replace array a_i with array b_i = a_i  -  a_i - 1, because all we care about are differences between neighboring elements. Now, we can see that our lost array can have length d if and only if for every j such that j  +  d  ≤  n, b_j  =  b_j + d. So we can iterate over every possible d from 1 to n and check if it is correct in O(n). Complexity of whole algorithm is O(n²).

#include <bits/stdc++.h>

using namespace std;

const int N = 1007;

int n;
int in[N];

bool ok(int d){
	for(int i = 0; i + d < n; ++i)
		if(in[i + 1] - in[i] != in[i + d + 1] - in[i + d])
			return false;
	return true;
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &in[i]);
	
	vector <int> res;
	for(int i = 1; i <= n; ++i)
		if(ok(i))
			res.push_back(i);
	
	printf("%d\n", res.size());
	for(int v: res)
		printf("%d ", v);
	return 0;
}

Basically in problem we are given a word in which for every i we can reverse prefix of first i elements and we want to get the smallest lexicographically word. We will show that we can always achieve word in form a^jb^n - j.

Let's say that we solved our problem for prefix of length i and for this prefix we have word a^jb^i - j (at the beginning it's just empty word). If our next letter is b then we do nothing, because we will get word a^jb^{i - j + 1} which is still the smallest lexicographically word. Otherwise we want to reverse prefix of length i, add letter a and reverse prefix of length i  +  1, so we get a word a^j + 1b^i - j, which is still fine for us.

There is still a problem — what if we have already reversed prefix i and we just said that we will reverse it second time. But instead of reversing it second time, we can deny it's first reverse.

Final complexity is O(n).

#include <bits/stdc++.h>

using namespace std;

const int N = 1007;

string s;
bool write[N];

int main(){
	cin >> s;
	for(int i = 1; i < s.size(); ++i)
		if(s[i] == 'a'){
			write[i - 1] ^= 1;
			write[i] = 1;
		}
	
	for(int i = 0; i < s.size(); ++i)
		printf("%d%c", write[i], i + 1 == (int)s.size() ? '\n' : ' ');
	return 0;
}

Deleting prefix and suffix is nothing more than taking a subarray. If subarray is common for all permutations then it has to appear in first permutation. We renumber all permutations such that first permutation is 1, 2, ..., n  -  1, n.

Now for every i in every permutation we count how long is subarray starting at i which looks like i, i  +  1, ..., i  +  k. It can be easily done in O(n) for one permutation with two pointers technique.

Now for every element i we compute reach[i] equal the longest subarray starting in i which looks like i, i  +  1, ..., i  +  k and it apears in all subarrays. It is just minimum over previously calculated values for all permutations.

Now we can see that our result is . Final complexity O(nm).

#include <bits/stdc++.h>

using namespace std;

typedef long long int LL;

const int N = 1e5 + 7;

int n, m;
int mn[N];
int ren[N];
int perm[15][N];

int main(){
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; ++i)
		for(int j = 1; j <= n; ++j)
			scanf("%d", &perm[i][j]);
	
	for(int i = 1; i <= n; ++i)
		ren[perm[1][i]] = i;
	
	for(int i = 1; i <= m; ++i)
		for(int j = 1; j <= n; ++j)
			perm[i][j] = ren[perm[i][j]];
		
	for(int i = 1; i <= n; ++i)
		mn[i] = n;
		
	for(int i = 1; i <= m; ++i){
		int cur = 1;
		for(int j = 1; j <= n; ++j){
			if(cur < j)
				++cur;

			while(cur < n && perm[i][cur + 1] == perm[i][cur] + 1)
				++cur;
			mn[perm[i][j]] = min(mn[perm[i][j]], perm[i][cur]);
		}
	}
	
	LL res = 0;
	int now = 1;
	while(now <= n){
		int cur = mn[now] - now + 1;
		res += 1LL * (cur + 1) * cur / 2LL;
		now = mn[now] + 1;
	}
	
	printf("%lld\n", res);
	return 0;
}

Let's compute result if there are no edges, we can add them later. If there are no edges then result for pair (i, j) is min(x_i  +  y_j, x_j  +  y_i). First let's fix i for which we want to compute result. Then calculate result with all pairs j such that x_i  +  y_j  ≤  x_j  +  y_i. After some transformations we get that x_i  -  y_i  ≤  x_j  -  y_j. Similarly we have that y_i  +  x_j  <  x_i  +  y_j if x_i  -  y_i  >  y_j  -  x_j.

So let's sort over differences of x_i  -  y_i and compute prefix sums of x_i and suffix sums of y_i. Now we can compute for every i result in O(1). Then we can iterate over every edge (u, v) and subtract min(x_u  +  y_v, x_v  +  y_u) from result of u and v.

Complexity O(nlogn).

#include <bits/stdc++.h>

using namespace std;

typedef long long int LL;

#define st first
#define nd second
#define PII pair <int, int>

const int N = 3e5 + 7;

int n, m;
PII diff[N];
int place[N];
vector <int> G[N];

LL ans[N];
int x[N], y[N];
LL pref[N], suf[N];

int main(){
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; ++i){
		scanf("%d %d", &x[i], &y[i]);
		diff[i] = {y[i] - x[i], i};
	}
	
	for(int i = 1; i <= m; ++i){
		int u, v;
		scanf("%d %d", &u, &v);

		G[u].push_back(v);
		G[v].push_back(u);
	}
	
	sort(diff + 1, diff + n + 1);
	for(int i = 1; i <= n; ++i)
		place[diff[i].nd] = i;
	
	for(int i = 1; i <= n; ++i)
		pref[i] = pref[i - 1] + y[diff[i].nd];
	
	for(int i = n; i >= 1; --i)
		suf[i] = suf[i + 1] + x[diff[i].nd];
	
	for(int i = 1; i <= n; ++i){
		int u = diff[i].nd;
		LL res = pref[i - 1] + suf[i + 1] + 1LL * (i - 1) * x[u] + 1LL * (n - i) * y[u];
		
		for(int v: G[u])
			res -= min(x[u] + y[v], x[v] + y[u]);
		ans[u] = res;
	}
	
	for(int i = 1; i <= n; ++i)
		printf("%lld ", ans[i]);
	return 0;
}

First let's observe that if there exists valid subset then it's size is at most 7 (because product of 7 smallest primes is bigger then 3 * 10⁵). Let's define dp[i][j] — number of ways to pick i different elements such that their gcd is equal to j. We can use inclusion--exclusion principle to calculate it. Then dp[i][j] = — , where cnt_j denotes number of a_i such that j | a_i. Because for k * j  >  3 * 10⁵, dp[i][k * j]  =  0 we have to check only k * j  ≤  3 * 10⁵.

Our answer is the smallest i such that dp[i][1] is non-zero. Since dp[i][j] can be quite big we should compute it modulo some big prime.

Final complexity is O(logM * (n + M)), where M is equal to maximum of a_i.

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 7;
const int MX = 1e9 + 7;

int n;
int cnt[N];
int sil[N];
int odw[N];
int dp[20][N];

int fast(int a, int b){
	int ret = 1;
	while(b){
		if(b & 1)
			ret = (1LL * ret * a)%MX;
		
		b >>= 1;
		a = (1LL * a * a)%MX;
	}
	
	return ret;
}

int newton(int a, int b){
	if(b < 0 || a < b)	return 0;
	return (((1LL * sil[a] * odw[b])%MX) * odw[a - b])%MX;
}

void sub(int &a, int b){
	a -= b;
	if(a < 0)
		a += MX;
}

int main(){
	sil[0] = 1;
	for(int i = 1; i < N; ++i)
		sil[i] = (1LL * sil[i - 1] * i)%MX;
	
	odw[N - 1] = fast(sil[N - 1], MX - 2);
	for(int i = N - 1; i >= 1; --i)
		odw[i - 1] = (1LL * odw[i] * i)%MX;

	scanf("%d", &n);
	for(int i = 1; i <= n; ++i){
		int a;
		scanf("%d", &a);
		cnt[a]++;
	}
	
	for(int i = 1; i < N; ++i)
		for(int j = i + i; j < N; j += i)
			cnt[i] += cnt[j];
	
	for(int i = 1; i < 20; ++i){
		for(int j = N - 1; j >= 1; --j){
			dp[i][j] = newton(cnt[j], i);
			for(int k = j + j; k < N; k += j)
				sub(dp[i][j], dp[i][k]);
		}
		
		if(dp[i][1] > 0){
			printf("%d\n", i);
			return 0;
		}
	}
	
	puts("-1");
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 7;

int n;
int cnt[N];
int roz[N];
int dist[N];
queue <int> Q;
vector <int> dv[N];

int base(int a){
	int ret = 1;
	while(a > 1){
		if(ret%roz[a] != 0)
			ret *= roz[a];
		a /= roz[a];
	}
	
	return ret;
}

void getEdges(int u, int d){
	vector <int> cur;
	vector <int> val;
	
	while(u > 1){
		cur.push_back(roz[u]);
		u /= roz[u];
	}
	
	for(int v: cur)
		u *= v;
	
	int T = 1 << (int)cur.size();
	val.resize(T);
	
	for(int i = 0; i < T; ++i){
		val[i] = u;
		for(int j = 0; j < (int)cur.size(); ++j)
			if(i & (1 << j))
				val[i] /= cur[j];
	}
	
	for(int i = 0; i < T; ++i){
		int s = 0;
		for(int j = i; true; j = (j - 1) & i){
			if(__builtin_popcount(i ^ j) & 1)
				s -= cnt[val[j]];
			else
				s += cnt[val[j]];
			
			if(j == 0)
				break;
		}
		
		assert(s >= 0);
		if(s && dist[val[i]] == -1){
			dist[val[i]] = d;
			Q.push(val[i]);
		}
	}
}

int main(){
	scanf("%d", &n);
	for(int i = 2; i < N; ++i){
		if(roz[i] != 0)
			continue;

		for(int j = i; j < N; j += i)
			roz[j] = i;
	}
	
	for(int i = 1; i < N; ++i)
		for(int j = i; j < N; j += i)
			dv[j].push_back(i);
	
	for(int i = 1; i < N; ++i)
		dist[i] = -1;
	
	for(int i = 1; i <= n; ++i){
		int a;
		scanf("%d", &a);
		a = base(a);
		
		if(dist[a] != -1)
			continue;

		dist[a] = 1;
		Q.push(a);
		
		for(int v: dv[a])
			cnt[v]++;
	}
	
	while(!Q.empty()){
		int u = Q.front();
		Q.pop();
		getEdges(u, dist[u] + 1);
	}
	
	printf("%d\n", dist[1]);
	return 0;
}

Let's solve the problem for some string s for any time.

Let's say, that partition of string s into k strings s_1s2... s_i1, s_i1 + 1... s_i2, ..., {s_{ik - 1 + 1}}... s_ik is good if at least one pair of this strings are equal. We want to find a minimal possible number of different strings in all good partitions.

It's easy to see, that the answer is  - 1 if and only if all symbols in s are different. And if we have two equal symbols s_i = s_j (i < j) we can cut a string into strings s₁... s_i - 1, s_i, s_i + 1... s_j - 1, s_j, s_j + 1... s_n and it is a good partition. In this partition there is at most 4 different strings.

So the answer can be  - 1, 1, 2, 3, 4.

The answer is  - 1 if all symbols in s are different (case 0).

The answer is 1 if the string s = aaa... a, for some string a (case 1).

The answer is 2 if the string s is aab, aba or baa for some strings a and b (case 2).

The answer is 3 if the string s is baac, bcaa or aabc for some strings a, b, c. In two last cases it's easy to see, that |a| = 1 (case 3).

To solve our problem let's build suffix array with lcp for string s. And let's find lt_i~--- minimal possible number r, such that s_isi + 1... s_r is a tandem (the string, that can be presented as aa for some string a) and rt_i~--- maximal possible number l such that s_lsl + 1... s_i is a tandem. This numbers can be found using Main and Lorentz algorithm for finding tandem repetitions in the string.

Now we can solve query for segment [l, r]: \begin{itemize} \item Case 0: if r - l ≥ 26, there exists equal symbols, otherwise we can check it by O(r - l); \item Case 1: to check that s[l... r] = aa... a we can see that |a| is a divisor of (r - l + 1) and (r - l + 1) / |a| is a prime number (if we take a longest possible string a). So we should check only O(log(n)) lenghts of string a; \item Case 2: s = aab lt_l ≤ r, s = baa rt_r ≥ l. In the last case we should check, that s[l... r] has a border. It's the most interesting part of the problem, let's solve it in the end; \item Case 3: s = abac s_l exists on s_l + 1... s_r (can be done using prefix sums), s = baca s_r exists on s_l... s_r - 1 (can be done using prefix sums). To check s = baac we can check, that lt_i ≤ r for some l ≤ i ≤ r, that can be done using minimum on segment in the array lt. \end{itemize}

Now we should the hardest part of this problem~--- we have some segments [l, r]. For all of them, we should check that the border of s[l... r] exists. Here I know two methods, that uses only suffix array. Easiest of them:

We have segment [l, r]. Let's check for all lengths , that s[l... (l + b - 1)] = s[(r - b + 1)... r]. If we don't find border, if it exists, it's length . Let's define i~--- maximal index i such that lcp(l, i) ≥ r - i + 1, and string s[i... r] is a border of s[l... r]. So . But it's easy to see, that the distance between l and i in suffix array , so we need to check only variants of i.

Another method can check that border exists for all segments [l, r] using offline algorithm by O(q·log(n)²) time.

So the total complexity will be or O((n + q)·log(n)²).

#include <bits/stdc++.h>

using namespace std;

const int BIG = 1e9 + 239;
const int M = 2 * 1e5 + 239;
const int L = 19;
const int A = 30;
const int T = (1 << 19);
const int two = 2;

int flm[two][M];

inline void z_function(string &s, int c)
{
	int n = s.length();
	flm[c][0] = 0;
	int l = 0;
	int r = 0;
	for (int i = 1; i < n; i++)
	{
		flm[c][i] = min(flm[c][i - l], r - i);
		if (flm[c][i] < 0) flm[c][i] = 0;
		while (i + flm[c][i] < n && s[flm[c][i]] == s[i + flm[c][i]]) flm[c][i]++;
		if (i + flm[c][i] > r)
		{
			l = i;
			r = i + flm[c][i];
		}
	}        
}

int a[M], lcp[M], pos[M];

inline void suffix_array(string s)
{
	s += (char)(31);
	int n = s.length();
	vector<pair<char, int> > v;
	for (int i = 0; i < n; i++)
		v.push_back(make_pair(s[i], i));
	sort(v.begin(), v.end());
	vector<pair<int, int> > num;
	int last = 0;
	for (int i = 0; i < n - 1; i++)
	{
		num.push_back(make_pair(last, v[i].second));
		if (v[i].first != v[i + 1].first) last++;
	}
	num.push_back(make_pair(last, v.back().second));
	vector<int> u(n);
	for (int i = 0; i < n; i++) u[num[i].second] = num[i].first;
	int d = 1;
	vector<pair<pair<int, int>, int> > t;
	vector<vector<pair<int, int> > > h;
	while (d < n)
	{
		t.clear();
		h.clear();
		h.resize(n);
		for (int i = 0; i < n; i++)
		{
			int l = num[i].second - d;
			if (l < 0) l += n;
			h[u[l]].push_back(make_pair(num[i].first, l));
		}
		for (int i = 0; i < n; i++)
			for (pair<int, int> r : h[i])
				t.push_back(make_pair(make_pair(i, r.first), r.second));
		last = 0;
		num.clear();
		for (int i = 0; i < n - 1; i++)
		{
			num.push_back(make_pair(last, t[i].second));
			if (t[i].first != t[i + 1].first) last++;
		}
		num.push_back(make_pair(last, t.back().second));
		for (int i = 0; i < n; i++) u[num[i].second] = num[i].first;
		d <<= 1;
	}                           
	for (int i = 1; i < n; i++) a[i - 1] = num[i].second;
}

string s;                 

inline void kasai()
{
	int n = s.size();
	suffix_array(s); 
	for (int i = 0; i < n; i++)
		pos[a[i]] = i;
	int k = 0;
	for (int i = 0; i < n; i++)
	{
		if (pos[i] == n - 1) continue;
		while (s[i + k] == s[a[pos[i] + 1] + k] && a[pos[i] + 1] + k < n && i + k < n) k++;
		lcp[pos[i]] = k;
		k = max(0, k - 1);
	}
}

int n, lw[M], rw[M]; 
string prr, rvl;                     
vector<int> open_l[M], close_l[M];   
vector<int> open_r[M], close_r[M];
multiset<int> nw;

inline void func(int l, int r)
{
	if (r - l == 1) return;
	int mid = (l + r) >> 1;
	func(l, mid);
	func(mid, r);
	rvl = "";
	for (int i = mid - 1; i >= l; i--) rvl += s[i];
	z_function(rvl, 0);
	prr = "";
	for (int i = mid; i < r; i++) prr += s[i];
	prr += '#';
	for (int i = l; i < mid; i++) prr += s[i];
	z_function(prr, 1);	
	for (int c = l; c < mid; c++)
	{
		int k1 = 0;
		if (c > l) k1 = flm[0][mid - c];
		int k2 = flm[1][r - mid + 1 + c - l];
		int len = mid - c;
		int lg = max(len - k2, 0);
		int rg = min(len - 1, k1);
		if (rg >= lg)
		{
			open_l[c - rg].push_back((2 * len));
			close_l[c - lg].push_back((2 * len));
			open_r[c - rg + 2 * len - 1].push_back((2 * len));
			close_r[c - lg + 2 * len - 1].push_back((2 * len));
		}	
	}
	rvl = "";
	for (int i = mid; i < r; i++) rvl += s[i];
	z_function(rvl, 0);
	prr = "";
	for (int i = mid - 1; i >= l; i--) prr += s[i];
	prr += '#';
	for (int i = r - 1; i >= mid; i--) prr += s[i];
	z_function(prr, 1); 
	for (int c = mid; c < r; c++)
	{
		int k1 = 0;
		if (c != r - 1) k1 = flm[0][c + 1 - mid];
		int k2 = flm[1][r - c + mid - l];
		int len = c - mid + 1;
		int lg = max(len - k2, 0);
		int rg = min(len - 1, k1);
		if (rg >= lg)
		{                                            
			open_l[c + lg - 2 * len + 1].push_back((2 * len));
			close_l[c + rg - 2 * len + 1].push_back((2 * len));
			open_r[c + lg].push_back((2 * len));
			close_r[c + rg].push_back((2 * len));
		}	
	}
	for (int i = l; i < r; i++)
	{
		for (int len : open_l[i]) nw.insert(len);
		if (!nw.empty()) lw[i] = min(lw[i], *nw.begin());
		for (int len : close_l[i]) nw.erase(nw.lower_bound(len));
		open_l[i].clear();
		close_l[i].clear();
	}          
	for (int i = l; i < r; i++)
	{
		for (int len : open_r[i]) nw.insert(len);
		if (!nw.empty()) rw[i] = min(rw[i], *nw.begin());
		for (int len : close_r[i]) nw.erase(nw.lower_bound(len));
		open_r[i].clear();
		close_r[i].clear();
	}
}

int mn[L][M], st2[M], lc[L][M], kol[A][M];

inline int getmin(int l, int r)
{
	int u = st2[r - l + 1];
	return min(mn[u][l], mn[u][r - (1 << u) + 1]);
}

inline int gett(int l, int r)
{
	if (l == r) return (n - l);
	l = pos[l];
	r = pos[r];
	if (l > r) swap(l, r);
	r--;
	int u = st2[r - l + 1];
	return min(lc[u][l], lc[u][r - (1 << u) + 1]);
}

int q, la[M], ra[M], has[M], mnp[M];

inline void init()
{
	for (int i = 0; i < n; i++) mn[0][i] = lw[i];
	for (int i = 0; i < n - 1; i++) lc[0][i] = lcp[i];
	for (int i = 1; i < L; i++)
		for (int j = 0; j < n; j++)
		{
			int r = (j + (1 << (i - 1)));
			if (r >= n)
			{
				mn[i][j] = mn[i - 1][j];
				continue;
			}
			mn[i][j] = min(mn[i - 1][j], mn[i - 1][r]);
		}
	for (int i = 1; i < L; i++)
		for (int j = 0; j < n - 1; j++)
		{
			int r = (j + (1 << (i - 1)));
			if (r >= n - 1)
			{
				lc[i][j] = lc[i - 1][j];
				continue;
			}                                          
			lc[i][j] = min(lc[i - 1][j], lc[i - 1][r]);
		}	
	st2[1] = 0;
	for (int i = 2; i <= n; i++)
	{
		st2[i] = st2[i - 1];
		if ((1 << (st2[i] + 1)) <= i) st2[i]++;
	}	
}

int in[L][M], gl[T];

inline void build(int i, int l, int r)
{
	if (i == 0) gl[i] = 0;
	else gl[i] = gl[(i - 1) / 2] + 1;
	if (r - l == 1)
	{
		in[gl[i]][l] = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(2 * i + 1, l, mid);
	build(2 * i + 2, mid, r);
	merge(in[gl[i] + 1] + l, in[gl[i] + 1] + mid, in[gl[i] + 1] + mid, in[gl[i] + 1] + r, in[gl[i]] + l);
}

inline bool is_on(int i, int l, int r, int ql, int qr, int xl, int xr)
{
	if (r <= ql || qr <= l) return false;
	if (ql <= l && r <= qr)
	{
		int it = upper_bound(in[gl[i]] + l, in[gl[i]] + r, xl) - in[gl[i]] - l;
		if (it == r - l) return false;
		return (in[gl[i]][it + l] <= xr);	
	}
	int mid = (l + r) >> 1;
	if (is_on(2 * i + 1, l, mid, ql, qr, xl, xr)) return true;
	return is_on(2 * i + 2, mid, r, ql, qr, xl, xr);
}

inline bool check_all(int l, int r)
{
	int len = (r - l + 1);
	int pl = pos[l];
	int lf = pl;
	int rf = n;
	while (rf - lf > 1)
	{
		int h = (lf + rf) / 2;
		if (gett(a[h], l) >= len) lf = h;
		else rf = h;
	}
	int rg = lf + 1;
	lf = -1;
	rf = pl;
	while (rf - lf > 1)
	{
		int h = (lf + rf) / 2;
		if (gett(a[h], l) >= len) rf = h;
		else lf = h;
	}
	int lg = rf;
	return is_on(0, 0, n, lg, rg, l, r);
}

int par[M];
set<int> cmp[M];
set<pair<int, int> > sc[M];
vector<int> ok[M];
vector<pair<int, int> > mg[M];

inline void border_check()
{
	for (int i = 0; i < q; i++) has[i] = false;
	for (int i = 0; i < q; i++) ok[ra[i] - la[i]].push_back(i);
	for (int i = 0; i < n - 1; i++) mg[lcp[i]].push_back(make_pair(a[i], a[i + 1]));
	for (int i = 0; i < n; i++)
	{
		par[i] = i;
		cmp[i].insert(i);
	}
	for (int c = n; c >= 1; c--)
	{
		for (int i : ok[c - 1])
			sc[par[la[i]]].insert(make_pair(ra[i], i));   
		for (pair<int, int> t : mg[c])
		{
			int l = par[t.first];
			int r = par[t.second];
			if (cmp[l].size() > cmp[r].size()) swap(l, r);
			for (int x : cmp[l])
				while (true)
				{
					auto it = sc[r].lower_bound(make_pair(x, 0));
					if (it == sc[r].end() || it->first > x + c - 1) break;
					has[it->second] = true;
					sc[r].erase(it);
				}
			for (pair<int, int> u : sc[l])
			{
				int id = u.second;
				auto uk = cmp[r].lower_bound(ra[id] - c + 1);
				if (uk != cmp[r].end() && (*uk) <= ra[id]) 
					has[id] = true;
				else 
				    sc[r].insert(u);
			}
			for (int x : cmp[l])
			{
				par[x] = r;
				cmp[r].insert(x);
			}
		}		
	}	
    for (int i = 0; i < q; i++)
	    if (!has[i] && check_all(la[i], ra[i]))
		{
			has[i] = true;
			continue;
		}
}

inline bool checkno(int l, int r)
{
	if (r - l + 1 > 26) return false;
	vector<int> kol(26, 0);
	for (int x = l; x <= r; x++)
	{
		if (kol[s[x] - 'a'] > 0) return false;
		kol[s[x] - 'a']++;
	}	
	return true;
}

inline bool try_kol(int l, int r, int p)
{
	int len = (r - l + 1) / p;
	return (gett(l, l + len) >= (r - l + 1 - len));
}

inline bool ison(int l, int r, char x)
{
	return (kol[x - 'a'][r + 1] > kol[x - 'a'][l]);	
}

inline int query(int l, int r, int id)
{         
	if (checkno(l, r)) return -1;
	int len = (r - l + 1);
	while (len > 1)
	{
		int p = mnp[len];
		if (try_kol(l, r, p)) return 1;
		while ((len % p) == 0) len /= p;
	}
	if (lw[l] <= r) return 2;
	if (rw[r] >= l) return 2;
	if (has[id]) return 2;
	if (ison(l + 1, r, s[l])) return 3;
	if (ison(l, r - 1, s[r])) return 3;
	if (getmin(l, r) <= r) return 3;	
	return 4;
}

int main()
{
	cin.sync_with_stdio(0); 
	cin >> n >> s;
	memset(mnp, -1, sizeof(mnp));
	for (int i = 2; i <= n; i++)
		if (mnp[i] == -1)
			for (int j = i; j <= n; j += i)
				if (mnp[j] == -1)
					mnp[j] = i;
	memset(kol[0], 0, sizeof(kol[0]));
	for (int i = 0; i < n; i++)
	{
		for (int x = 0; x < 26; x++) kol[x][i + 1] = kol[x][i];
		kol[s[i] - 'a'][i + 1]++;
	}
	for (int i = 0; i < n; i++)
	{
		lw[i] = n + 1;
		rw[i] = n + 1;
	}
	func(0, n);  
	for (int i = 0; i < n; i++)
	{
		if (lw[i] == n + 1) lw[i] = n;
		else lw[i] += (i - 1);  
		if (rw[i] == n + 1) rw[i] = -1;
		else rw[i] = (i - rw[i] + 1);
	}
	kasai();                                                                        
	init();  
	build(0, 0, n);                                                                       
	cin >> q;
	for (int i = 0; i < q; i++)
	{
		cin >> la[i] >> ra[i];
		la[i]--, ra[i]--;                       
	}
	border_check();
	for (int i = 0; i < q; i++) cout << query(la[i], ra[i], i) << "\n";
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)

const int BIG = 1e9 + 239;
const int M = 2 * 1e5 + 239;
const int L = 19;
const int A = 30;
const int T = (1 << 19);
const int two = 2;

int flm[two][M];

inline void z_function(string &s, int c)
{
	int n = s.length();
	flm[c][0] = 0;
	int l = 0;
	int r = 0;
	for (int i = 1; i < n; i++)
	{
		flm[c][i] = min(flm[c][i - l], r - i);
		if (flm[c][i] < 0) flm[c][i] = 0;
		while (i + flm[c][i] < n && s[flm[c][i]] == s[i + flm[c][i]]) flm[c][i]++;
		if (i + flm[c][i] > r)
		{
			l = i;
			r = i + flm[c][i];
		}
	}        
}

int a[M], lcp[M], pos[M];

inline void suffix_array(string s)
{
	s += (char)(31);
	int n = s.length();
	vector<pair<char, int> > v;
	for (int i = 0; i < n; i++)
		v.push_back(make_pair(s[i], i));
	sort(v.begin(), v.end());
	vector<pair<int, int> > num;
	int last = 0;
	for (int i = 0; i < n - 1; i++)
	{
		num.push_back(make_pair(last, v[i].second));
		if (v[i].first != v[i + 1].first) last++;
	}
	num.push_back(make_pair(last, v.back().second));
	vector<int> u(n);
	for (int i = 0; i < n; i++) u[num[i].second] = num[i].first;
	int d = 1;
	vector<pair<pair<int, int>, int> > t;
	vector<vector<pair<int, int> > > h;
	while (d < n)
	{
		t.clear();
		h.clear();
		h.resize(n);
		for (int i = 0; i < n; i++)
		{
			int l = num[i].second - d;
			if (l < 0) l += n;
			h[u[l]].push_back(make_pair(num[i].first, l));
		}
		for (int i = 0; i < n; i++)
			for (pair<int, int> r : h[i])
				t.push_back(make_pair(make_pair(i, r.first), r.second));
		last = 0;
		num.clear();
		for (int i = 0; i < n - 1; i++)
		{
			num.push_back(make_pair(last, t[i].second));
			if (t[i].first != t[i + 1].first) last++;
		}
		num.push_back(make_pair(last, t.back().second));
		for (int i = 0; i < n; i++) u[num[i].second] = num[i].first;
		d <<= 1;
	}                           
	for (int i = 1; i < n; i++) a[i - 1] = num[i].second;
}

string s;                 

inline void kasai()
{
	int n = s.size();
	suffix_array(s); 
	for (int i = 0; i < n; i++)
		pos[a[i]] = i;
	int k = 0;
	for (int i = 0; i < n; i++)
	{
		if (pos[i] == n - 1) continue;
		while (s[i + k] == s[a[pos[i] + 1] + k] && a[pos[i] + 1] + k < n && i + k < n) k++;
		lcp[pos[i]] = k;
		k = max(0, k - 1);
	}
}

int n, lw[M], rw[M]; 
string prr, rvl;                     
vector<int> open_l[M], close_l[M];   
vector<int> open_r[M], close_r[M];
multiset<int> nw;

inline void func(int l, int r)
{
	if (r - l == 1) return;
	int mid = (l + r) >> 1;
	func(l, mid);
	func(mid, r);
	rvl = "";
	for (int i = mid - 1; i >= l; i--) rvl += s[i];
	z_function(rvl, 0);
	prr = "";
	for (int i = mid; i < r; i++) prr += s[i];
	prr += '#';
	for (int i = l; i < mid; i++) prr += s[i];
	z_function(prr, 1);	
	for (int c = l; c < mid; c++)
	{
		int k1 = 0;
		if (c > l) k1 = flm[0][mid - c];
		int k2 = flm[1][r - mid + 1 + c - l];
		int len = mid - c;
		int lg = max(len - k2, 0);
		int rg = min(len - 1, k1);
		if (rg >= lg)
		{
			open_l[c - rg].push_back((2 * len));
			close_l[c - lg].push_back((2 * len));
			open_r[c - rg + 2 * len - 1].push_back((2 * len));
			close_r[c - lg + 2 * len - 1].push_back((2 * len));
		}	
	}
	rvl = "";
	for (int i = mid; i < r; i++) rvl += s[i];
	z_function(rvl, 0);
	prr = "";
	for (int i = mid - 1; i >= l; i--) prr += s[i];
	prr += '#';
	for (int i = r - 1; i >= mid; i--) prr += s[i];
	z_function(prr, 1); 
	for (int c = mid; c < r; c++)
	{
		int k1 = 0;
		if (c != r - 1) k1 = flm[0][c + 1 - mid];
		int k2 = flm[1][r - c + mid - l];
		int len = c - mid + 1;
		int lg = max(len - k2, 0);
		int rg = min(len - 1, k1);
		if (rg >= lg)
		{                                            
			open_l[c + lg - 2 * len + 1].push_back((2 * len));
			close_l[c + rg - 2 * len + 1].push_back((2 * len));
			open_r[c + lg].push_back((2 * len));
			close_r[c + rg].push_back((2 * len));
		}	
	}
	for (int i = l; i < r; i++)
	{
		for (int len : open_l[i]) nw.insert(len);
		if (!nw.empty()) lw[i] = min(lw[i], *nw.begin());
		for (int len : close_l[i]) nw.erase(nw.lower_bound(len));
		open_l[i].clear();
		close_l[i].clear();
	}          
	for (int i = l; i < r; i++)
	{
		for (int len : open_r[i]) nw.insert(len);
		if (!nw.empty()) rw[i] = min(rw[i], *nw.begin());
		for (int len : close_r[i]) nw.erase(nw.lower_bound(len));
		open_r[i].clear();
		close_r[i].clear();
	}
}

int mn[L][M], st2[M], lc[L][M], kol[A][M];

inline int getmin(int l, int r)
{
	int u = st2[r - l + 1];
	return min(mn[u][l], mn[u][r - (1 << u) + 1]);
}

inline int gett(int l, int r)
{
	if (l == r) return (n - l);
	l = pos[l];
	r = pos[r];
	if (l > r) swap(l, r);
	r--;
	int u = st2[r - l + 1];
	return min(lc[u][l], lc[u][r - (1 << u) + 1]);
}

int q, mnp[M];

inline void init()
{
	for (int i = 0; i < n; i++) mn[0][i] = lw[i];
	for (int i = 0; i < n - 1; i++) lc[0][i] = lcp[i];
	for (int i = 1; i < L; i++)
		for (int j = 0; j < n; j++)
		{
			int r = (j + (1 << (i - 1)));
			if (r >= n)
			{
				mn[i][j] = mn[i - 1][j];
				continue;
			}
			mn[i][j] = min(mn[i - 1][j], mn[i - 1][r]);
		}
	for (int i = 1; i < L; i++)
		for (int j = 0; j < n - 1; j++)
		{
			int r = (j + (1 << (i - 1)));
			if (r >= n - 1)
			{
				lc[i][j] = lc[i - 1][j];
				continue;
			}                                          
			lc[i][j] = min(lc[i - 1][j], lc[i - 1][r]);
		}	
	st2[1] = 0;
	for (int i = 2; i <= n; i++)
	{
		st2[i] = st2[i - 1];
		if ((1 << (st2[i] + 1)) <= i) st2[i]++;
	}	
}

int u, len;

inline bool check(int l, int r)
{
	for (int t = 1; t <= min(len, ((r - l + 1) / 2)); t++)
		if (gett(l, r - t + 1) >= t)
			return true;
	for (int i = max(0, pos[l] - len); i <= min(n - 1, pos[l] + len); i++)
		if (l < a[i] && a[i] <= r && gett(l, a[i]) >= r - a[i] + 1) 
			return true;
	return false;
}

inline bool checkno(int l, int r)
{
	if (r - l + 1 > 26) return false;
	vector<int> kol(26, 0);
	for (int x = l; x <= r; x++)
	{
		if (kol[s[x] - 'a'] > 0) return false;
		kol[s[x] - 'a']++;
	}	
	return true;
}

inline bool try_kol(int l, int r, int p)
{
	int len = (r - l + 1) / p;
	return (gett(l, l + len) >= (r - l + 1 - len));
}

inline bool ison(int l, int r, char x)
{
	return (kol[x - 'a'][r + 1] > kol[x - 'a'][l]);	
}

inline int query(int l, int r)
{         
	if (checkno(l, r)) return -1;
	int len = (r - l + 1);
	while (len > 1)
	{
		int p = mnp[len];
		if (try_kol(l, r, p)) return 1;
		while ((len % p) == 0) len /= p;
	}
	if (lw[l] <= r) return 2;
	if (rw[r] >= l) return 2;
	if (check(l, r)) return 2;
	if (ison(l + 1, r, s[l])) return 3;
	if (ison(l, r - 1, s[r])) return 3;
	if (getmin(l, r) <= r) return 3;	
	return 4;
}

int main()
{
	cin.sync_with_stdio(0); 
	cin >> n >> s;
	memset(mnp, -1, sizeof(mnp));
	for (int i = 2; i <= n; i++)
		if (mnp[i] == -1)
			for (int j = i; j <= n; j += i)
				if (mnp[j] == -1)
					mnp[j] = i;
	memset(kol[0], 0, sizeof(kol[0]));
	for (int i = 0; i < n; i++)
	{
		for (int x = 0; x < 26; x++) kol[x][i + 1] = kol[x][i];
		kol[s[i] - 'a'][i + 1]++;
	}
	for (int i = 0; i < n; i++)
	{
		lw[i] = n + 1;
		rw[i] = n + 1;
	}
	func(0, n);  
	for (int i = 0; i < n; i++)
	{
		if (lw[i] == n + 1) lw[i] = n;
		else lw[i] += (i - 1);  
		if (rw[i] == n + 1) rw[i] = -1;
		else rw[i] = (i - rw[i] + 1);
	}
	kasai();                                                                        
	init();  
	cin >> q;
	for (int i = 0; i < n; i++)
		if (i * i >= n)
		{
			len = i + 3;
			break;
		}
	for (int i = 0; i < q; i++)
	{
		int l, r;
		cin >> l >> r;
		l--, r--;
		cout << query(l, r) << "\n";                       
	}
	return 0;
}