#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using ll=long long;
using mint=modint998244353;
const int b=550;
using ar=array<int,3>;
int d,w;
ll op(ll x,ll y){
    return min(x,y);
}
ll e(){
    return 1e9;
}

bool F(ll x){
    return x>=d;
}
int main()
{
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)a[i]=min(a[i],n);
    vector<vector<segtree<ll,op,e>>> stv((n+b)/b,vector<segtree<ll,op,e>>(3));
    for(int i=0;i<3;i++)stv[0][i]=segtree<ll,op,e>(vector<ll>(n+1,-1));
    for(int i=1;i<(n+b)/b;i++){
        stv[i]=stv[i-1];
        for(int j=(i-1)*b;j<min(n,i*b);j++){
            stv[i][2].set(a[j],stv[i][1].get(a[j]));
            stv[i][1].set(a[j],stv[i][0].get(a[j]));
            stv[i][0].set(a[j],j);
        }
    }
    ll key=0;
    int q;
    cin>>q;
    while(q--){
        ll x,y;
        cin>>x>>y;
        x^=key;y^=key;
        x--;
        int p=y/b;
        vector<ll> rec;
        for(int i=p*b;i<y;i++){
            rec.push_back(stv[p][2].get(a[i]));
            stv[p][2].set(a[i],stv[p][1].get(a[i]));
            stv[p][1].set(a[i],stv[p][0].get(a[i]));
            stv[p][0].set(a[i],i);
        }
        int ans=0;
        for(int i=0;i<3;i++){
            d=x;
            ans+=min((ll)(stv[p][i].max_right<F>(0)),y-x-2);
        }
        cout<<ans<<endl;
        key=ans;
        reverse(rec.begin(),rec.end());
        for(int i=y-1;i>=p*b;i--){
            int j=y-1-i;
            stv[p][0].set(a[i],stv[p][1].get(a[i]));
            stv[p][1].set(a[i],stv[p][2].get(a[i]));
            stv[p][2].set(a[i],rec[j]);
        }
    }

    
    return 0;
}