#include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 using namespace std;

 #define N 50001

 #define BLOCK_SIZE 250

 int sz,sum,n,a[N],l[BLOCK_SIZE],r[BLOCK_SIZE],D[N],f[BLOCK_SIZE][BLOCK_SIZE];

 int Less[BLOCK_SIZE][N],More[BLOCK_SIZE][N],b[N],en,m,x,y,num[N],ans;

 struct Point{int v,p;}t[N];

 bool operator < (const Point &a,const Point &b){return a.v<b.v;}

 int Res,Num;char C,CH[];

 inline int G()

 {

     Res=;C='*';

     while(C<''||C>'')C=getchar();

     while(C>=''&&C<=''){Res=Res*+(C-'');C=getchar();}

     return Res;

 }

 inline void P(int x)

 {

     Num=;if(!x){putchar('');puts("");return;}

     while(x>)CH[++Num]=x%,x/=;

     while(Num)putchar(CH[Num--]+);

     puts("");

 }

 void add(int p,const int &v) {while(p<=n) {D[p]+=v; p+=(p&(-p));}}

 int getsum(int p) {int res=; while(p) {res+=D[p]; p-=(p&(-p));} return res;}

 void makeblock()

 {

     sz=sqrt(n); if(!sz) sz=;

     for(sum=;sum*sz<n;sum++)

       {

           l[sum]=r[sum-]+;

           r[sum]=sum*sz;

           for(int i=l[sum];i<=r[sum];i++) num[i]=sum;

       }

     l[sum]=r[sum-]+;

     r[sum]=n;

     for(int i=l[sum];i<=r[sum];i++) num[i]=sum;

 }

 void LiSan()

 {

     sort(t+,t+n+); a[t[].p]=++en;

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

       {

           if(t[i].v!=t[i-].v) en++;

           a[t[i].p]=en;

       }

 }

 void init_each_ans()

 {

     for(int i=;i<=sum;i++)

       {

           memset(D,,sizeof(D)); int pos=,res=;

           for(int j=i;j<=sum;j++)

             {

                 for(int k=l[j];k<=r[j];k++)

                   {

                       pos++;

                       add(a[k],);

                       res+=(pos-getsum(a[k]));

                   }

                 f[i][j]=res;

             }

       } memset(D,,sizeof(D));

 }

 void init_sum()

 {

     memcpy(b,a,sizeof(b));

     for(int i=;i<=sum;i++)

       {

         sort(b+l[i],b+r[i]+);

           memcpy(More[i],More[i-],sizeof(More[i]));

           memcpy(Less[i],Less[i-],sizeof(Less[i]));

           for(int j=;j<=en;j++)

             {

                 More[i][j]+=(b+r[i]+-upper_bound(b+l[i],b+r[i]+,j));

                 Less[i][j]+=(lower_bound(b+l[i],b+r[i]+,j)-(b+l[i]));

             }

       }

 }

 int getMore(const int &L,const int &R,const int &v){return More[R][v]-More[L-][v];}

 int getLess(const int &L,const int &R,const int &v){return Less[R][v]-Less[L-][v];}

 int main()

 {

     n=G();

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

       {

           t[i].v=G();

           t[i].p=i;

       }

     LiSan(); makeblock(); init_each_ans(); init_sum();

     m=G();

     for(int j=;j<=m;j++)

       {

           x=G(); y=G(); x^=ans; y^=ans;

           if(num[x]+>=num[y])

             {

                 int pos=; ans=;

                 for(int i=x;i<=y;i++)

                   {

                       pos++;

                       add(a[i],);

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

                   }

                 for(int i=x;i<=y;i++) add(a[i],-);

               P(ans);

             }

           else

             {

                 int pos=r[num[x]]-x+; ans=f[num[x]+][num[y]-];

                 for(int i=r[num[x]];i>=x;i--)

                   {

                       ans+=(getLess(num[x]+,num[y]-,a[i])+getsum(a[i]-));

                       add(a[i],);

                   }

                 for(int i=l[num[y]];i<=y;i++)

                   {

                       pos++;

                       add(a[i],);

                       ans+=(pos-getsum(a[i])+getMore(num[x]+,num[y]-,a[i]));

                   }

                 for(int i=x;i<=r[num[x]];i++) add(a[i],-);

                 for(int i=l[num[y]];i<=y;i++) add(a[i],-);

               P(ans);

             }

       }

     return ;

 }