#include <iostream>
#include <vector>
#include <cmath>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
struct Node {
int minpoz;
int st, dr;
};
struct Query {
int left, right, ind;
};
int n, q;
int cnt, ind;
int v[600005];
pair<int, int> qs[600005];
Node pool[15000005];
int root[600005];
// Am marit limitele si sters matricea "bin" nefolosita pentru a elibera memorie
vector<Query> qs_mex[600005];
int frec[600005];
int nxt[600005];
vector<int> vec[600005];
vector<pair<int, int>> qs_node[600005];
int path[600005];
vector<int> rez;
void update(int cur, int prev, int left, int right, int poz, int val) {
if(left == right) {
pool[cur].minpoz = val;
return;
}
int mij = (left + right) / 2;
if(poz <= mij) {
cnt++;
pool[cur].st = cnt;
pool[pool[cur].st] = pool[pool[prev].st];
pool[cur].dr = pool[prev].dr;
update(pool[cur].st, pool[prev].st, left, mij, poz, val);
} else {
cnt++;
pool[cur].dr = cnt;
pool[pool[cur].dr] = pool[pool[prev].dr];
pool[cur].st = pool[prev].st;
update(pool[cur].dr, pool[prev].dr, mij+1, right, poz, val);
}
pool[cur].minpoz = min(pool[pool[cur].st].minpoz, pool[pool[cur].dr].minpoz);
}
int find_mex(int node, int left, int right, int st) {
if(left == right) {
return left;
}
int mij = (left + right) / 2;
if(pool[pool[node].st].minpoz < st) {
return find_mex(pool[node].st, left, mij, st);
} else {
return find_mex(pool[node].dr, mij+1, right, st);
}
}
int query(int node, int left, int right, int qleft, int qright) {
if(qright < left || right < qleft) {
return n + 1;
}
if(qleft <= left && right <= qright) {
return pool[node].minpoz;
}
int mij = (left + right) / 2;
return min(query(pool[node].st, left, mij, qleft, qright),
query(pool[node].dr, mij+1, right, qleft, qright));
}
void dfs(int nod) {
int true_nod = nod - 1;
for(auto it: qs_node[nod]) {
int poz = lower_bound(path + 1, path + ind + 1, it.first - 1) - path;
int ans = ind - poz + 1;
rez[it.second - 1] = ans;
}
ind++;
path[ind] = true_nod;
for(auto it: vec[nod]) {
dfs(it);
}
ind--;
}
std::vector<int> solve(int N, std::vector<int> &init, int Q, std::vector<std::pair<int, int>> &initqs) {
n = N;
q = Q;
// Resetam constantele in caz ca functia este rulata pentru mai multe teste
cnt = 0;
ind = 0;
pool[0] = {0, 0, 0};
// Curatam qs_mex raportat la N + 1
for(int i = 0; i <= n + 2; i++) {
qs_mex[i].clear();
}
for(int i = 0; i < n; i++) {
v[i + 1] = init[i];
}
for(int i = 0; i < q; i++) {
qs[i + 1] = initqs[i];
qs[i + 1].first++;
qs[i + 1].second++;
}
root[0] = 0;
for(int i = 1; i <= n; i++) {
// Inseram doar valorile valide ca sa nu corupem frunzele limitei superioare din arbore
if (v[i] >= 1 && v[i] <= n + 2) {
cnt++;
root[i] = cnt;
update(root[i], root[i - 1], 1, n + 2, v[i], i);
} else {
root[i] = root[i - 1]; // Pastram starea veche
}
}
rez.assign(q, 0); // Assign sterge valorile reziduale sigure
for(int i = 1; i <= q; i++) {
// Adaptam limita la n + 2
int mex = find_mex(root[qs[i].second], 1, n + 2, qs[i].first);
if(mex == 1) {
rez[i - 1] = qs[i].second - qs[i].first + 1;
continue;
}
qs_mex[mex].push_back({qs[i].first, qs[i].second, i});
}
// Adaptam for-ul doar pana la n + 1. MEX-ul nu poate depasi N + 1.
for(int i = 2; i <= n + 1; i++) {
if(qs_mex[i].size() == 0) {
continue;
}
long long cost_sim = 1LL * qs_mex[i].size() * (n / i) * 15LL;
long long cost_bin = 1LL * n;
if(cost_bin > cost_sim) { // simulez simplu
for(auto it: qs_mex[i]) {
int ans = 0;
int cur = it.right;
while(cur >= it.left) {
int nxt_val = query(root[cur], 1, n + 2, 1, i - 1);
if(nxt_val < it.left) {
break;
}
ans++;
cur = nxt_val - 1;
}
rez[it.ind - 1] = ans;
}
} else {
for(int j = 1; j <= i; j++) {
frec[j] = 0;
}
int st = 1;
int dr = 1;
int distinct = 0;
while(dr <= n) {
if(v[dr] < i) {
frec[v[dr]]++;
if(frec[v[dr]] == 1) {
distinct++;
}
}
while(distinct >= i - 1) {
if(v[st] < i) {
if(frec[v[st]] == 1) {
if(distinct == i - 1) {
break;
}
distinct--;
}
frec[v[st]]--;
}
st++;
}
if(distinct == i - 1) {
nxt[dr] = st;
} else {
nxt[dr] = 0;
}
dr++;
}
// Folosim o variabila 'j' diferita pentru a nu face "shadowing" pe variabila 'i' din for-ul parinte
for(int j = 0; j <= n; j++) {
vec[j].clear();
qs_node[j].clear();
}
vec[0].push_back(1);
for(int j = 1; j <= n; j++) {
vec[nxt[j]].push_back(j + 1);
}
for(auto it: qs_mex[i]) {
qs_node[it.right + 1].push_back({it.left, it.ind});
}
ind = 0;
dfs(0);
}
}
return rez;
}
