#include <bits/stdc++.h>
using namespace std;
static const int MAXV = 400000;
static const int B = 700;
vector<int> solve(
int n, vector<int>& v,
int q, vector<pair<int,int>>& queries
) {
/* ---------------- POSITIONS ---------------- */
vector<vector<int>> pos(MAXV + 2);
for (int i = 0; i < n; i++)
pos[v[i]].push_back(i);
/* ---------------- MEX OFFLINE ---------------- */
vector<int> last(MAXV + 2, -1);
vector<vector<int>> qs(n);
for (int i = 0; i < q; i++)
qs[queries[i].second].push_back(i);
vector<int> mex(q);
set<int> missing;
for (int i = 1; i <= MAXV + 1; i++)
missing.insert(i);
for (int i = 0; i < n; i++) {
int x = v[i];
if (last[x] == -1)
missing.erase(x);
last[x] = i;
for (int qi : qs[i]) {
int l = queries[qi].first;
while (!missing.empty()) {
int m = *missing.begin();
if (last[m] >= l) {
missing.erase(m);
} else break;
}
mex[qi] = *missing.begin();
}
}
/* ---------------- nextEnd PRECOMPUTE ---------------- */
vector<vector<int>> nextEnd(B + 1, vector<int>(n, n));
for (int m = 1; m <= B; m++) {
vector<int> cnt(m, 0);
int need = m - 1;
int have = 0;
int r = 0;
for (int l = 0; l < n; l++) {
while (r < n && have < need) {
if (v[r] < m) {
if (++cnt[v[r]] == 1)
have++;
}
r++;
}
if (have == need)
nextEnd[m][l] = r - 1;
if (v[l] < m) {
if (--cnt[v[l]] == 0)
have--;
}
}
}
/* ---------------- ANSWER QUERIES ---------------- */
vector<int> ans(q);
for (int i = 0; i < q; i++) {
int l = queries[i].first;
int r = queries[i].second;
int m = mex[i];
int cur = l;
int cnt = 0;
if (m <= B) {
while (cur <= r) {
int e = nextEnd[m][cur];
if (e > r) break;
cnt++;
cur = e + 1;
}
} else {
while (cur <= r) {
int e = cur;
for (int x = 1; x < m; x++) {
auto it = lower_bound(pos[x].begin(), pos[x].end(), cur);
if (it == pos[x].end()) {
e = n;
break;
}
e = max(e, *it);
}
if (e > r) break;
cnt++;
cur = e + 1;
}
}
ans[i] = cnt;
}
return ans;
}
