#include<bits/stdc++.h>

#define N 50005

#define pa pair<int,int>

#define fi first

#define sc second

using namespace std;

int n,m,cnt,tot,size,t;

int a[N],c[N],num[N],rt[N];

int sum[][N];

inline int lowbit(int x){return (x&(-x));}

pa b[N];

struct Persistenable_Segment_Tree{

    int ls[*N],rs[*N],size[*N],cnt;

    void ins(int &x,int pre,int l,int r,int q){

        x=++cnt;size[x]=size[pre]+;

        if(l==r)return;

        ls[x]=ls[pre];rs[x]=rs[pre];

        int mid=(l+r)>>;

        if(q<=mid)ins(ls[x],ls[pre],l,mid,q);

        else ins(rs[x],rs[pre],mid+,r,q);

    }

    int query(int x,int pre,int l,int r,int ql,int qr){

        if(size[x]==size[pre])return ;

        if(ql<=l&&r<=qr)return size[pre]-size[x];

        int mid=(l+r)>>,ans=;

        if(ql<=mid)ans+=query(ls[x],ls[pre],l,mid,ql,qr);

        if(qr>mid)ans+=query(rs[x],rs[pre],mid+,r,ql,qr);

        return ans;

    }

}T;

inline void add(int x,int val){

    for(int i=x;i<=tot;i+=lowbit(i))c[i]+=val;

}

inline int ask(int x){

    int ans=;

    for(int i=x;i;i-=lowbit(i))ans+=c[i];

    return ans;

}

//bit

int query(int x,int y){

    int ans=;

    if(num[x]==num[y]){

        memset(c,,sizeof(c));

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

        return ans;

    }

    ans=sum[num[x]+][y];

    for(register int i=x;i<=size*num[x];++i)ans+=T.query(rt[i],rt[y],,tot,,a[i]-);

    return ans;

}

//block

inline int read(){

    int f=,x=;char ch;

    do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');

    do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');

    return f*x;

}

int LastOrder=;

int main(){

    n=read();size=round(sqrt(n));

    for(int i=;i<=n;i++)b[i].fi=read(),b[i].sc=i;

    sort(b+,b+n+);

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

        if(i==|b[i].fi!=b[i-].fi)++tot;

        a[b[i].sc]=tot;

    }

    for(int i=;i<=n;i++)T.ins(rt[i],rt[i-],,tot,a[i]);

    for(int i=;i<=n;i++)num[i]=(i-)/size+;

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

        memset(c,,sizeof(c));

        for(int j=(i-)*size+;j<=n;j++){

            sum[i][j]=sum[i][j-]+ask(tot)-ask(a[j]);

            add(a[j],);

        }

    }

    m=read();

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

        int x=read(),y=read();x^=LastOrder;y^=LastOrder;

        LastOrder=query(x,y);

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

    }

    return ;

}