#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
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;
};
using b = bitset<75005>;
const int BLOCK = 275;
b T; for (int i = 1; i <= n; i++) T.set(i);
T[75004] = 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) {
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;
bool found = true;
while (found) {
found = false;
while (lo < hi) {
int mid = lo + (hi-lo) / 2;
int cmex = range_mex(L, mid);
if (cmex == mex) hi = mid;
else lo = mid + 1;
}
found = range_mex(L, lo) == mex;
if (found) {
u++;
lo = L = lo+1;
hi = r;
}
}
ans.push_back(u);
}
return ans;
}
