#include<bits/stdc++.h>
using namespace std;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
int n, q;
vector<int>a;
vector<pair<int, int>>query;
namespace sub123{
const int lim = 1e3 + 5;
bitset<lim>cnt;
vector<int>solve(){
vector<int>ret;
for(auto& [l, r] : query){
cnt.reset();
int mex_lr = 1;
for(int i = l; i <= r; i++){
cnt[a[i]] = true;
while(cnt[mex_lr]){
mex_lr++;
}
}
if(mex_lr == 1){
ret.push_back(r - l + 1);
continue;
}
int ans = 0;
for(int i = l; i <= r; ){
cnt.reset();
int mex = 1;
while(i <= r && mex < mex_lr){
cnt[a[i++]] = true;
while(cnt[mex]){
mex++;
}
}
if(mex < mex_lr){
break;
}
ans++;
}
ret.push_back(ans);
}
return ret;
}
}
namespace sub4{
vector<int>solve(){
for(int& x : a){
x--;
}
vector<vector<int>>nxt(n + 1, vector<int>(2, n)), up(20, vector<int>(n + 2, n + 1));
for(int i = n - 2; i > -1; i--){
nxt[i] = nxt[i + 1];
nxt[i][a[i + 1]] = i + 1;
}
for(int i = 0; i < n; i++){
up[0][i] = nxt[i][a[i] ^ 1] + 1;
}
for(int i = 1; i < 20; i++){
for(int j = 0; j < n; j++){
up[i][j] = up[i - 1][up[i - 1][j]];
}
}
vector<int>ret;
for(auto& [l, r] : query){
int ans = 0;
for(int bit = 19; bit > -1; bit--){
if(up[bit][l] < r + 2){
l = up[bit][l];
ans |= 1 << bit;
}
}
ret.push_back(ans == 0 ? r - l + 1 : ans);
}
return ret;
}
}
namespace sub56{
const int lim = 6e5 + 5;
const int LIM = 4e5 + 5;
int st[LIM << 2], in_pos[LIM];
vector<int>mex_1, mex_2, ans, event[lim];
void update(int id, int l, int r, int p, int x){
if(l == r){
st[id] = x;
return;
}
int m = (l + r) >> 1;
if(m < p){
update(id << 1 | 1, m + 1, r, p, x);
}
else{
update(id << 1, l, m, p, x);
}
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
int walk(int x){
int id = 1, l = 1, r = LIM;
while(l < r){
int m = (l + r) >> 1;
if(st[id <<= 1] >= x){
id |= 1;
l = m + 1;
}
else{
r = m;
}
}
return l;
}
vector<int>work(){
memset(st, -1, sizeof(st));
for(int i = 0; i < n; i++){
event[i].clear();
}
for(int i = 0; i < q; i++){
if(query[i].first <= query[i].second){
event[query[i].second].push_back(i);
}
}
vector<int>mex(q, 0);
for(int r = 0; r < n; r++){
update(1, 1, LIM, a[r], r);
for(int& i : event[r]){
mex[i] = walk(query[i].first);
}
}
return mex;
}
struct Data{
int mex, cnt, last;
Data(){}
Data(int _mex, int _cnt, int _last) : mex(_mex), cnt(_cnt), last(_last) {}
};
Data left[lim], right[lim];
void dnc(int l, int r){
if(l > r){
return;
}
int m = (l + r) >> 1;
left[m] = Data(0, 0, m);
set<int>s;
for(int i = m - 1, mex = 1; i >= l; i--){
if(in_pos[a[i]] != -1 && a[i] < mex){
s.erase(in_pos[a[i]]);
}
if(a[in_pos[a[i]] = i] < mex){
s.insert(i);
}
while(in_pos[mex] != -1){
s.insert(in_pos[mex++]);
}
if(mex == 1){
left[i] = Data(1, m - i, m);
}
else if(mex != left[i + 1].mex){
left[i] = Data(mex, 1, *s.rbegin() + 1);
}
else{
int other = *s.rbegin() + 1;
if(left[other].mex == mex){
left[i] = left[other];
left[i].cnt++;
}
else{
left[i] = Data(mex, 1, other);
}
}
}
s.clear();
for(int i = m - 1; i >= l; i--){
in_pos[a[i]] = -1;
}
if(m > 0){
right[m - 1] = Data(0, 0, m - 1);
}
for(int i = m, mex = 1; i <= r; i++){
if(in_pos[a[i]] != -1 && a[i] < mex){
s.erase(in_pos[a[i]]);
}
if(a[in_pos[a[i]] = i] < mex){
s.insert(i);
}
while(in_pos[mex] != -1){
s.insert(in_pos[mex++]);
}
if(mex == 1){
right[i] = Data(1, i - m + 1, m - 1);
}
else if(i == m || mex != right[i - 1].mex){
right[i] = Data(mex, 1, *s.begin() - 1);
}
else{
int other = *s.begin() - 1;
if(other != -1 && right[other].mex == mex){
right[i] = right[other];
right[i].cnt++;
}
else{
right[i] = Data(mex, 1, other);
}
}
while(!event[i].empty()){
int qid = event[i].back();
auto& [lq, rq] = query[qid];
if(lq > m){
break;
}
event[i].pop_back();
if(right[rq].mex == mex_1[qid]){
ans[qid] += right[rq].cnt;
rq = right[rq].last;
}
if(left[lq].mex == mex_1[qid]){
ans[qid] += left[lq].cnt;
lq = left[lq].last;
}
}
}
for(int i = m; i <= r; i++){
in_pos[a[i]] = -1;
}
dnc(l, m - 1);
dnc(m + 1, r);
}
vector<int>solve(){
mex_1 = work();
for(int i = 0; i < n; i++){
sort(event[i].begin(), event[i].end(), [&] (int x, int y){
return query[x].first > query[y].first;
});
}
memset(in_pos, -1, sizeof(in_pos));
ans.assign(q, 0);
dnc(0, n - 1);
mex_2 = work();
for(int i = 0; i < q; i++){
if(mex_1[i] == mex_2[i]){
ans[i]++;
}
}
return ans;
}
}
vector<int>solve(int __n, vector<int>& __v, int __q, vector<pair<int, int>>& __query){
a = __v;
n = __n;
query = __query;
for(int& i : a){
minimize(i, n + 2);
}
if(max(n, q = __q) <= 1000){
return sub123::solve();
}
if(*max_element(a.begin(), a.end()) < 3){
return sub4::solve();
}
return sub56::solve();
}
