#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1e9;
// Segment Tree for finding MEX offline
struct MexSegTree {
int n;
vector<int> tree;
MexSegTree(int n) : n(n), tree(4 * n + 4, INF) {}
void update(int node, int start, int end, int idx, int val) {
if (start == end) {
tree[node] = val;
return;
}
int mid = (start + end) / 2;
if (idx <= mid) update(2 * node, start, mid, idx, val);
else update(2 * node + 1, mid + 1, end, idx, val);
tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}
int query(int node, int start, int end, int limit) {
if (start == end) return start;
int mid = (start + end) / 2;
if (tree[2 * node] > limit) return query(2 * node, start, mid, limit);
return query(2 * node + 1, mid + 1, end, limit);
}
};
// Segment Tree for lazy Range Chmax and Point Query
struct JumpSegTree {
int n;
vector<int> lazy;
JumpSegTree(int n) : n(n), lazy(2 * n, 0) {}
void range_chmax(int l, int r, int val) {
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) { lazy[l] = max(lazy[l], val); l++; }
if (r & 1) { r--; lazy[r] = max(lazy[r], val); }
}
}
int point_query(int p) {
int res = 0;
for (p += n; p > 0; p >>= 1) {
res = max(res, lazy[p]);
}
return res;
}
};
struct Query {
int l, r, id, mex;
};
vector<int> path_st;
vector<int> ans;
vector<vector<pair<int, int>>> node_queries;
vector<vector<int>> adj;
void dfs(int u, int depth) {
path_st.push_back(u);
for (auto& q : node_queries[u]) {
int limit = q.first;
int q_id = q.second;
auto it = lower_bound(path_st.begin(), path_st.end(), limit, greater<int>());
int idx = distance(path_st.begin(), it);
ans[q_id] = depth - idx;
}
for (int v : adj[u]) {
dfs(v, depth + 1);
}
path_st.pop_back();
}
vector<int> solve(int n, vector<int>& v, int q, vector<pair<int, int>>& queries) {
vector<Query> Q(q);
for (int i = 0; i < q; i++) {
Q[i] = {queries[i].first, queries[i].second, i, 0};
}
// Sort queries by L descending for offline MEX finding
vector<int> order(q);
for (int i = 0; i < q; i++) order[i] = i;
sort(order.begin(), order.end(), [&](int a, int b) {
return Q[a].l > Q[b].l;
});
MexSegTree mex_st(n + 2);
int curr_l = n;
for (int idx : order) {
while (curr_l > Q[idx].l) {
curr_l--;
mex_st.update(1, 1, n + 2, v[curr_l], curr_l);
}
Q[idx].mex = mex_st.query(1, 1, n + 2, Q[idx].r);
}
vector<vector<int>> queries_by_M(n + 3);
for (int i = 0; i < q; i++) {
queries_by_M[Q[i].mex].push_back(i);
}
vector<vector<int>> pos(n + 2);
for (int i = 0; i < n; i++) {
pos[v[i]].push_back(i);
}
JumpSegTree jst(n + 2);
ans.assign(q, 0);
int B = 800; // Threshold
for (int M = 1; M <= n + 1; M++) {
if (M > 1) {
int prev = 0;
for (int p : pos[M - 1]) {
jst.range_chmax(prev, p, p);
prev = p + 1;
}
if (prev <= n) {
jst.range_chmax(prev, n, n + 1); // Jump out of bounds
}
}
if (queries_by_M[M].empty()) continue;
if (M <= B) {
// Reconstruct array explicitly and build tree
vector<int> F(n + 1);
vector<int> tmp = jst.lazy;
for (int i = 1; i < jst.n; i++) {
tmp[2 * i] = max(tmp[2 * i], tmp[i]);
tmp[2 * i + 1] = max(tmp[2 * i + 1], tmp[i]);
}
adj.assign(n + 3, vector<int>());
node_queries.assign(n + 3, vector<pair<int, int>>());
for (int i = 0; i <= n; i++) {
F[i] = tmp[jst.n + i];
int next_node = F[i] + 1;
if (next_node > n + 1) next_node = n + 2; // dummy root
adj[next_node].push_back(i);
}
for (int idx : queries_by_M[M]) {
node_queries[Q[idx].l].push_back({Q[idx].r + 1, Q[idx].id});
}
path_st.clear();
dfs(n + 2, 0);
} else {
// For large M simulate greedily
for (int idx : queries_by_M[M]) {
int curr = Q[idx].l;
int r = Q[idx].r;
int count = 0;
while (curr <= r) {
int next_start = jst.point_query(curr) + 1;
if (next_start <= r + 1) {
count++;
curr = next_start;
} else {
break;
}
}
ans[Q[idx].id] = count;
}
}
}
return ans;
}
