#include <bits/stdc++.h>
using namespace std;
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define F0R(i, r) FOR(i, 0, r)
#define FORD(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define F0RD(i, r) FORD(i, 0, r)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define uniquify(v) v.erase(unique(all(v)), end(v))
#define ff first
#define ss second
#define mp make_pair
#define mt make_tuple
#define dbg(x) "[" #x " = " << (x) << "]"
#define tcT template<class T
tcT> bool minimize(T& a, const T& b){ return a > b ? a = b, 1 : 0; }
tcT> bool maximize(T& a, const T& b){ return a < b ? a = b, 1 : 0; }
tcT> using vc = vector<T>;
tcT> using vvc = vc<vc<T>>;
using ll = long long;
using db = double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vc<int>;
using vl = vc<ll>;
using vpi = vc<pi>;
using vpl = vc<pl>;
using vvi = vvc<int>;
using vvl = vvc<ll>;
using vvpi = vvc<pi>;
using vvpl = vvc<pl>;
#define ls (lc[s])
#define rs (rc[s])
const int MAX = 1e6 + 5;
const int MAXNODES = MAX * 20;
int nodes, lc[MAXNODES], rc[MAXNODES], minpos[MAXNODES];
int createNode(){
++nodes;
return nodes;
}
void pull(int s){
minpos[s] = min(minpos[ls], minpos[rs]);
}
int update(int s, int l, int r, int pos, int val){
if(l == r){
int ns = createNode();
minpos[ns] = val;
return ns;
} else{
int mid = l + r >> 1, ns = createNode();
lc[ns] = ls;
rc[ns] = rs;
if(pos <= mid) lc[ns] = update(ls, l, mid, pos, val);
else rc[ns] = update(rs, mid + 1, r, pos, val);
pull(ns);
return ns;
}
}
int query(int s, int l, int r, int bound){
if(l == r) return l;
int mid = l + r >> 1;
if(minpos[ls] < bound) return query(ls, l, mid, bound);
return query(rs, mid + 1, r, bound);
}
vi solve(int N, vi& _A, int Q, vpi& queries){
vi A(N + 1);
int bound = 0;
F0R(i, N) maximize(bound, A[i + 1] = min(_A[i], N + 1));
++bound;
F0R(i, Q){
++queries[i].ff, ++queries[i].ss;
}
vi ans(Q), ver(N + 1);
for(int i = 1; i <= N; ++i){
ver[i] = update(ver[i - 1], 1, bound, A[i], i);
}
auto findMex = [&](int l, int r){
return query(ver[r], 1, bound, l);
};
vvi queriesByMex(N + 2);
F0R(i, Q){
auto [L, R] = queries[i];
int mex = findMex(L, R);
if(mex == 1){
ans[i] = R - L + 1;
} else{
queriesByMex[mex].eb(i);
}
}
vvi positionsByValue(N + 2);
FOR(i, 1, N + 1) positionsByValue[A[i]].eb(i);
auto findNext = [&](int x, int from){ //from < pos
int pos = upper_bound(all(positionsByValue[x]), from) - positionsByValue[x].begin();
return pos == sz(positionsByValue[x]) ? -1 : positionsByValue[x][pos];
};
auto findPrevious = [&](int x, int to){ //pos < to
int pos = lower_bound(all(positionsByValue[x]), to) - positionsByValue[x].begin();
return pos == 0 ? -1 : positionsByValue[x][pos - 1];
};
//find minimum mex intervals
vvpi minimumMexIntervals(N + 2);
FOR(i, 1, N + 1){
if(A[i] == 1){
minimumMexIntervals[2].eb(i, i);
}
}
for(int mex = 2; mex <= N + 1; ++mex){
vpi& intervals = minimumMexIntervals[mex];
sort(all(intervals));
F0R(i, sz(intervals)){
auto [l, r] = intervals[i];
int x = findPrevious(mex, l);
if(x != -1 && (i == 0 || (intervals[i - 1].ss < x))){
int newMex = findMex(x, r);
assert(mex < newMex);
minimumMexIntervals[newMex].eb(x, r);
}
int y = findNext(mex, r);
if(y != -1 && (i + 1 == sz(intervals) || (intervals[i + 1].ff > y))){
int newMex = findMex(l, y);
assert(mex < newMex);
minimumMexIntervals[newMex].eb(l, y);
}
}
if(!queriesByMex[mex].empty()){
const int B = 18;
int siz = sz(intervals);
vector<array<int, B>> jump(siz);
int ptr = 0;
F0R(i, siz){
++intervals[i].ss;
while(ptr < siz && intervals[i].ss > intervals[ptr].ff) ++ptr;
jump[i][0] = ptr;
}
F0RD(i, siz){
FOR(j, 1, B){
if(jump[i][j - 1] == siz){
jump[i][j] = siz;
} else{
jump[i][j] = jump[jump[i][j - 1]][j - 1];
}
}
}
for(auto id : queriesByMex[mex]){
auto [L, R] = queries[id];
++R;
int u = lower_bound(all(intervals), mp(L, -1)) - intervals.begin();
if(u < siz) F0RD(i, B){
if(jump[u][i] != siz && intervals[jump[u][i]].ss <= R){
ans[id] += (1 << i);
u = jump[u][i];
}
}
if(u < siz && intervals[u].ss <= R) ++ans[id];
}
}
}
return ans;
}
