#include<cstdio>
#include<cmath>
#include<cctype>
#include<algorithm>
using namespace std;
const int N=1e5+5,M=405;
int dd[M][M][M],da1[M][N][2],n,m,a[N],qs,qc,be[M],en[M],nq[N],px[N],lx[2][N];
long long da[M][M];
class istream{
    char buf[13000003],*s;
    public:
        inline istream(){
            buf[fread(s=buf,1,13000001,stdin)]='\n';
        }
        template<typename T>
        inline void operator>>(T&rhs){
            for(rhs=0;!isdigit(*s);++s);
            while(isdigit(*s))rhs=rhs*10+(*s++&15);
		}
}in;
struct ostream{
    char buf[8000005],*s;
    inline ostream(){s=buf;}
    inline void operator<<(long long d){
        if(!d){
            *s++='0';
        }else{
            static long long w;
            for(w=1;w<=d;w*=10);
            for(;w/=10;d%=w)*s++=d/w^'0';
        }
        *s++='\n';
    }
    inline ostream&operator<<(const char&c){*s++=c;return*this;}
    inline~ostream(){fwrite(buf,1,s-buf,stdout);}
}out;
//0-> >  1->
long long mer(int *l,int *r,int le1,int le2){
	int l1=1,r1=1;
	long long ans=0;
	while(l1<=le1 && r1<=le2){
		if(l[l1]>r[r1]){
			ans+=le1-l1+1;
			r1++;
		}
		else l1++;
	}
	return ans;
}
inline int d(int i,int j,int k,int v){
	return da1[j][k][v]-da1[i-1][k][v];
}
bool cmp(int A,int B){
	return a[A]<a[B];
}
int main(){
	in>>n;
	in>>m;
	qc=sqrt(n);
	qs=(n+qc-1)/qc;
	for(int i=1;i<=n;i++){
		in>>a[i];
		nq[i]=(i+qc-1)/qc;
		px[i]=i;
	}
	for(int i=1;i<=qs;i++){
		be[i]=(i-1)*qc+1;
		en[i]=be[i]+qc-1;
	}
	en[qs]=n;
	for(int i=1;i<=qs;i++) sort(px+be[i],px+en[i]+1,cmp);
	for(int i=1;i<=qs;i++){
		for(int le=2;le<=en[i]-be[i]+1;le++){
			for(int l=be[i];l<=en[i]-le+1;l++){
				int r=l+le-1,l1=l-be[i],r1=r-be[i];
				dd[i][l1][r1]=dd[i][l1][r1-1]+dd[i][l1+1][r1]-dd[i][l1+1][r1-1]+(a[l]>a[r]);
			}
		}
		for(int j=be[i];j<=en[i];j++){
			da1[i][a[j]-1][0]++; 
			da1[i][a[j]+1][1]++;
		}
		da[i][i]=dd[i][0][en[i]-be[i]];
		for(int j=n;j>=1;j--) da1[i][j][0]+=da1[i][j+1][0];
		for(int j=1;j<=n;j++) da1[i][j][1]+=da1[i][j-1][1];
		for(int j=1;j<=n;j++) da1[i][j][0]+=da1[i-1][j][0],da1[i][j][1]+=da1[i-1][j][1];
	}
	for(int le=2;le<=qs;le++){
		for(int l=1;l<=qs-le+1;l++){
			int r=le+l-1;
			da[l][r]=da[l][r-1]+da[r][r];
			for(int i=be[r];i<=en[r];i++) da[l][r]+=d(l,r-1,a[i],0);
		}
	}
	long long ans=0;
	while(m--){
		long long l,r;
		in>>l;
		in>>r;
		l^=ans;
		r^=ans;
		ans=0;
		if(nq[l]==nq[r]){
			ans=dd[nq[l]][l-be[nq[l]]][r-be[nq[l]]];
			out<<ans;
			continue;
		}
		ans=da[nq[l]+1][nq[r]-1]+
		dd[nq[l]][l-be[nq[l]]][en[nq[l]]-be[nq[l]]]+dd[nq[r]][0][r-be[nq[r]]];
		for(int i=l;i<=en[nq[l]];i++) ans+=d(nq[l]+1,nq[r]-1,a[i],1);
		for(int i=be[nq[r]];i<=r;i++) ans+=d(nq[l]+1,nq[r]-1,a[i],0);
		lx[0][0]=lx[1][0]=0;
		for(int i=be[nq[l]];i<=en[nq[l]];i++) if(px[i]>=l) lx[0][++lx[0][0]]=a[px[i]];
		for(int i=be[nq[r]];i<=en[nq[r]];i++) if(px[i]<=r) lx[1][++lx[1][0]]=a[px[i]];
		ans+=mer(lx[0],lx[1],lx[0][0],lx[1][0]);
		out<<ans;
	}
	return 0;
}