#include <iostream>
#include <vector>
#include <cmath>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
struct Node
{
int minpoz;
int st, dr;
};
struct Query
{
int left, right, ind;
};
int n, q;
int cnt;
int v[600005];
pair<int, int> qs[600005];
Node pool[15000005];
int root[600005];
vector<Query> qs_mex[400005];
int bin[23][600005];
void update(int cur, int prev, int left, int right, int poz, int val)
{
if(left == right)
{
pool[cur].minpoz = val;
return;
}
int mij = (left + right) / 2;
if(poz <= mij)
{
cnt++;
pool[cur].st = cnt;
pool[pool[cur].st] = pool[pool[prev].st];
pool[cur].dr = pool[prev].dr;
update(pool[cur].st, pool[prev].st, left, mij, poz, val);
}
else
{
cnt++;
pool[cur].dr = cnt;
pool[pool[cur].dr] = pool[pool[prev].dr];
pool[cur].st = pool[prev].st;
update(pool[cur].dr, pool[prev].dr, mij+1, right, poz, val);
}
pool[cur].minpoz = min(pool[pool[cur].st].minpoz, pool[pool[cur].dr].minpoz);
}
int find_mex(int node, int left, int right, int st)
{
if(left == right)
{
return left;
}
int mij = (left + right) / 2;
if(pool[pool[node].st].minpoz < st)
{
return find_mex(pool[node].st, left, mij, st);
}
else
{
return find_mex(pool[node].dr, mij+1, right, st);
}
}
int query(int node, int left, int right, int qleft, int qright)
{
if(qright < left || right < qleft)
{
return n + 1;
}
if(qleft <= left && right <= qright)
{
return pool[node].minpoz;
}
int mij = (left + right) / 2;
return min(query(pool[node].st, left, mij, qleft, qright),
query(pool[node].dr, mij+1, right, qleft, qright));
}
std::vector<int> solve(int N, std::vector<int> &init, int Q, std::vector<std::pair<int, int>> &initqs)
{
n = N;
q = Q;
for(int i = 0; i<n; i++)
{
v[i + 1] = init[i];
}
for(int i = 0; i<q; i++)
{
qs[i + 1] = initqs[i];
qs[i + 1].first++;
qs[i + 1].second++;
}
for(int i = 1; i<=n; i++)
{
cnt++;
root[i] = cnt;
update(root[i], root[i - 1], 1, 4e5, v[i], i);
}
vector<int> rez;
rez.resize(q);
for(int i = 1; i<=q; i++)
{
int mex = find_mex(root[qs[i].second], 1, 4e5, qs[i].first);
if(mex == 1)
{
rez[i - 1] = qs[i].second - qs[i].first + 1;
continue;
}
qs_mex[mex].push_back({qs[i].first, qs[i].second, i});
}
int SQ = sqrt(n);
int LG = log2(n);
for(int i = 2; i<=min(400001, n + 1); i++)
{
if(qs_mex[i].size() == 0)
{
continue;
}
if(qs_mex[i].size() <= 10) //e mai bine sa fac aia mare, decat sa precalculez tot binary lifting-ul
{
for(auto it: qs_mex[i])
{
int ans = 0;
int cur = it.right;
while(cur >= it.left)
{
int nxt = query(root[cur], 1, 4e5, 1, i - 1);
if(nxt < it.left)
{
break;
}
ans++;
cur = nxt - 1;
}
rez[it.ind - 1] = ans;
}
continue;
}
if(i > SQ)
{
for(auto it: qs_mex[i])
{
int ans = 0;
int cur = it.right;
while(cur >= it.left)
{
int nxt = query(root[cur], 1, 4e5, 1, i - 1);
if(nxt < it.left)
{
break;
}
ans++;
cur = nxt - 1;
}
rez[it.ind - 1] = ans;
}
}
else
{
for(int j = 1; j<=n; j++)
{
bin[0][j] = query(root[j], 1, 4e5, 1, i - 1);
}
LG = log2(n / (i - 1)); //numarul maxim de subsecvente
for(int k = 1; k <= LG; k++)
{
for(int j = 1; j<=n; j++)
{
if(bin[k - 1][j] == 0)
{
bin[k][j] = 0;
}
else
{
bin[k][j] = bin[k - 1][bin[k - 1][j] - 1];
}
}
}
for(auto it: qs_mex[i])
{
int ans = 0;
int poz = it.right;
for(int bit = LG; bit>=0; bit--)
{
if(bin[bit][poz] >= it.left)
{
ans += (1 << bit);
poz = bin[bit][poz] - 1;
}
}
rez[it.ind - 1] = ans;
}
}
}
return rez;
}
