#include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int N=;

 int n,Block,a[N],b[N],block[N],R[],L[],f[][],tr[][N],m,ans;

 int lowbit(int x){

     return x&-x;

 }

 void add(int id,int x,int w){

     for(int i=x;i<=n;i+=lowbit(i)){

         tr[id][i]+=w;

     }

 }

 int getsum(int id,int x){

     int tmp=;

     for(int i=x;i;i-=lowbit(i)){

         tmp+=tr[id][i];

     }

     return tmp;

 }

 int main(){

     scanf("%d",&n);

     Block=sqrt(n);

     for(int i=;i<=n;i++){

         scanf("%d",&a[i]);

         b[i]=a[i];

         block[i]=(i-)/Block+;

         if(!L[block[i]])L[block[i]]=i;

         R[block[i]]=i;

     }

     sort(b,b++n);

     int tot=unique(b+,b++n)-b-;

     for(int i=;i<=n;i++){

         a[i]=lower_bound(b+,b++tot,a[i])-b;

     }

     for(int i=;i<=block[n];i++){

         for(int j=L[i];j<=n;j++){

             add(i,a[j],);

         }

     }

     for(int i=;i<=block[n];i++){

         int tot=;

         for(int j=L[i];j<=n;j++){

             add(,a[j],);

             tot+=getsum(,n)-getsum(,a[j]);

             f[i][block[j]]=tot;

         }

         for(int j=L[i];j<=n;j++){

             add(,a[j],-);

         }

     }

     scanf("%d",&m);

     while(m--){

         int l,r;

         scanf("%d%d",&l,&r);

         l=l^ans;r=r^ans;

         if(l>r)swap(l,r);

         if(l==||r==||l>n||r>n)continue;

         if(block[l]+>=block[r]){

             ans=;

             for(int i=l;i<=r;i++){

                 add(,a[i],);

                 ans+=getsum(,n)-getsum(,a[i]);

             }

             for(int i=l;i<=r;i++){

                 add(,a[i],-);

             }

         }

         else{

             ans=f[block[l]+][block[r]-];

             int size=L[block[r]]-R[block[l]]-;

         //    cout<<ans<<" "<<size<<"sdjksd"<<endl;

             for(int i=l;i<=R[block[l]];i++){

                 ans+=getsum(block[l]+,a[i]-)-getsum(block[r],a[i]-);

                 add(,a[i],);

                 ans+=getsum(,n)-getsum(,a[i]);

             }

             for(int i=L[block[r]];i<=r;i++){

                 ans+=size-(getsum(block[l]+,a[i])-getsum(block[r],a[i]));

                 add(,a[i],);

                 ans+=getsum(,n)-getsum(,a[i]);

             }

             for(int i=l;i<=R[block[l]];i++){

                 add(,a[i],-);

             }

             for(int i=L[block[r]];i<=r;i++){

                 add(,a[i],-);

             }

         }

         printf("%d\n",ans);

     }

     return ;

 }