#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using pi = pair<int, int>;
using vpi = vector<pi>;
template<class T> bool chmin(T& a, const T& b) {return b < a ? a = b, 1 : 0;}
template<class T> bool chmax(T& a, const T& b) {return a < b ? a = b, 1 : 0;}
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
#define rep(i, a, b) for (int i = a; i < b; i++)
#define rev(i, a, b) for (int i = a; i >= b; i--)
#define sz(x) int((x).size())
#ifdef LOCAL
#define dbg(x) cerr << #x << " = " << x << "\n"
#else
#define dbg(x)
#endif
int maxv = 75005;
struct vertex {
int v = -1;
vertex *f = nullptr, *g = nullptr;
vertex(int v = -1) : v(v) {}
vertex(vertex *F, vertex *G) {
f = F; g = G;
v = min(F->v, G->v);
}
};
struct segtree {
int n; vector<vertex*> roots;
segtree(int n = 0) : n(n) {roots.push_back(new vertex());}
vertex* update(vertex* cur, int l, int r, int k, int v) {
if (!cur) cur = new vertex();
if (!(l <= k && k < r)) return cur;
if (l + 1 == r) return cur = new vertex(v);
int m = l + (r-l) / 2;
return new vertex(update(cur->f, l, m, k, v), update(cur->g, m, r, k, v));
}
int query(vertex* cur, int l, int r, int ql, int qr) {
if (!cur) cur = new vertex();
if (qr <= l || r <= ql) return 1e9;
if (ql <= l && r <= qr) return cur->v;
int m = l + (r-l) / 2;
return min(query(cur->f, l, m, ql, qr), query(cur->g, m, r, ql, qr));
}
void update(int k, int v) {
roots.push_back(update(roots.back(), 0, n, k, v));
}
int walk(int l, int r) {
return walk(roots[r+1], 0, n, l);
}
int walk(vertex* cur, int l, int r, int ql) {
if (!cur) cur = new vertex();
if (l + 1 == r) return l;
int m = l + (r-l) / 2;
if (!cur->f || cur->f->v < ql) return walk(cur->f, l, m, ql);
else return walk(cur->g, m, r, ql);
}
};
vi solve(int n, vi& v, int q, vpi& queries) {
vi ans;
rep(i, 0, n) if (v[i] > n) v[i] = 0;
vvi pos(n+1);
rep(i, 0, n) {
if (v[i] > n) continue;
pos[v[i]].push_back(i);
}
auto first_ge = [&](int i, int x) {
auto it = lower_bound(all(pos[x]), i);
return it == en(pos[x]) ? -1 : *it;
};
auto range_contains = [&](int l, int r, int x) {
if (pos[x].empty()) return false;
auto it = lower_bound(all(pos[x]), l);
if (it == en(pos[x])) return false;
return *it <= r;
};
segtree pst(maxv);
for (int i = 0; i < n; i++) pst.update(v[i]-1, i);
using b = bitset<75005>;
const int BLOCK = 275;
b T; for (int i = 1; i <= n; i++) T.set(i);
T[n+1] = 1;
vector<b> SQRT(BLOCK, T);
for (int i = 0; i < n; i++) {
SQRT[i/BLOCK][v[i]] = 0;
}
auto range_mex = [&](int l, int r) {
return pst.walk(l, r);
// auto start = T; int i = l;
// for (; i <= r && i % BLOCK != 0; i++) start[v[i]] = 0;
// for (; i + BLOCK - 1 <= r; i+=BLOCK) {
// start &= SQRT[i/BLOCK];
// }
// for (; i <= r; i++) start[v[i]] = 0;
// return start._Find_first();
};
for (auto &[l, r] : queries) {
// set<int> x; rep(i, l, r+1) x.insert(v[i]);
// int mex = 1; while (x.count(mex)) mex++;
int mex = range_mex(l, r);
int u = 0;
// set<int> y; int cmex = 1;
// rep(i, l, r+1) {
// y.insert(v[i]);
// while (y.count(cmex)) cmex++;
// if (cmex == mex) {
// u++; y.clear(); cmex = 1;
// }
// }
int lo = l, hi = r;
int L = l, R = r;
while (L <= r && range_mex(L, r) == mex) {
int lo = L, hi = r;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (range_mex(L, mid) == mex) hi = mid;
else lo = mid + 1;
}
u++;
L = lo + 1;
}
ans.push_back(u);
}
return ans;
}
