#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pp pair<ll, ll>
#define vp vector<pp>
#define inf 1000000000
#define mod 1000000007
vp Itree;
void init(ll n){
Itree.clear();
while(n & (n - 1)) n++;
Itree.resize(2*n, {-inf, -1});
}
void update(pp val, ll ind){
ind += Itree.size() / 2;
Itree[ind] = val;
while(ind > 1){
ind /= 2;
Itree[ind] = max(Itree[2*ind], Itree[2*ind + 1]);
}
}
pp get2(ll u, ll l, ll r, ll a, ll b){
if(l == a && r == b){
return Itree[u];
}
ll s = (a + b) / 2;
if(r <= s) return get2(2*u, l, r, a, s);
else if(l >= s) return get2(2*u + 1, l, r, s, b);
else return max(get2(2*u, l, s, a, s), get2(2*u + 1, s, r, s, b));
}
pp get(ll l, ll r){
return get2(1, l, r, 0, Itree.size() / 2);
}
ll getMex(ll l, ll r){
ll akt = Itree.size()/ 2;
ll val = Itree[akt].first;
while(val < r){
if(akt & 1) akt++;
else akt /= 2;
val = max(val, Itree[akt].first);
}
while(2*akt < Itree.size()){
if(Itree[2*akt].first >= r){
akt *= 2;
}else akt = 2*akt + 1;
}
return Itree[akt].second;
}
vector<int> solve(int n, vector<int>& A, int q, vector<pair<int, int>>& queries){
for(int i = 0; i < A.size(); i++) A[i]--;
vi next(n, inf);
map<ll, ll> mp;
vi b(n, inf);
for(int i = n - 1; i >= 0; i--){
if(A[i] > b.size()) continue;
next[i] = b[A[i]];
b[A[i]] = i;
}
vi c(b.size());
for(int i = 0; i < b.size(); i++) c[i] = b[i];
ll sm = min((ll)(sqrt(n) + 100), (ll)n);
ll jumps = log2(n) + 5;
vector<vvi> up(sm, vvi(n, vi(jumps, inf)));
for(int i = 0; i < n; i++){
ll mx = -1;
for(int j = 0; j < sm; j++){
mx = max(mx, b[j]);
up[j][i][1] = mx;
}
if(A[i] > b.size()) continue;
b[A[i]] = next[i];
}
for(int k = 2; k < jumps; k++){
for(int j = 0; j < sm; j++){
for(int i = 0; i < n; i++){
ll u = up[j][i][k - 1] + 1;
if(u >= n) continue;
up[j][i][k] = up[j][u][k - 1];
}
}
}
vvi quer(n + 2);
vector<int> ans(q, 0);
vi mex(q, -1);
for(int i = 0; i < q; i++){
pp x = queries[i];
quer[x.first].push_back(i);
}
init(c.size());
for(int i = 0; i < c.size(); i++) update({c[i], i}, i);
for(int i = 0; i < n; i++){
for(int j = 0; j < quer[i].size(); j++){
ll ind = quer[i][j];
if(mex[ind] == -1){
mex[ind] = getMex(0, queries[ind].second);
}
ll mx = mex[ind];
if(mx == 0){
ans[ind] = queries[ind].second - queries[ind].first + 1;
continue;
}
if(mex[ind] < sm){
ll akt = i;
ll cnt = up[mx - 1][akt].size() - 1;
while(cnt > 0){
if(up[mx - 1][akt][cnt] <= queries[ind].second){
akt = up[mx - 1][akt][cnt] + 1;
ans[ind] += (1 << (cnt - 1));
}
if(akt > queries[ind].second) break;
cnt--;
}
}else{
pp xd = get(0, mx);
ll kam = xd.first;
if(kam <= queries[ind].second) {
ans[ind]++;
quer[kam + 1].push_back(ind);
}
}
}
if(A[i] > c.size()) continue;
c[A[i]] = next[i];
update({c[A[i]], A[i]}, A[i]);
}
return ans;
}
/*
int main(){
cin.tie(0);
ios_base::sync_with_stdio(false);
vector<int> A = {1, 2, 567, 1, 2, 65, 1, 2, 34};
vector<pair<int, int>> q = {{1, 2}};
vector<int> x = solve(9, A, 1, q);
for(ll a : x){
cout << a << '\n';
}
}*/
