rt

#include<bits/stdc++.h>
#define int long long
#define maxn 120000
#define bmaxn (int)sqrt(120000)+20
using namespace std;
inline int read() {
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)) {
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(isdigit(ch)) {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int n,m,blen,bsize;
int a[maxn],id[maxn];
int c[bmaxn][maxn],ans[bmaxn][bmaxn];
int cc[maxn];
int lastans;
inline int lowbit(int x) {
	return x&-x;
}
void add(int x,int v) {
	for( ; x<=n; x+=lowbit(x)) cc[x]+=v;
}
int sum(int x) {
	int s=0;
	for( ; x>0; x-=lowbit(x)) s+=cc[x];
	return s;
}
struct block {
	int l,r,cnt;
	int pre[bmaxn],suf[bmaxn];
	pair<int,int> k[bmaxn];
} b[bmaxn];
int t1[bmaxn],tt1;
int t2[maxn],tt2;
signed main() {
	n=read(),m=read();
	for(int i=1; i<=n; i++) a[i]=read();
	blen=sqrt(n),bsize=ceil(n*1.0/blen);
	for(int i=1; i<=bsize; i++) {
		b[i].l=(i-1)*blen+1,b[i].r=min(i*blen,n),b[i].cnt=b[i].r-b[i].l+1;
		int cnt=0;
		for(int j=b[i].l; j<=b[i].r; j++) {
			id[j]=i;
			b[i].k[++cnt]=make_pair(a[j],j);
			b[i].pre[cnt]=b[i].pre[cnt-1]+(sum(n)-sum(a[j]));
			add(a[j],1);
			++c[i][a[j]];
		}
		ans[i][i]=b[i].pre[cnt];
		sort(b[i].k+1,b[i].k+cnt+1);
		memset(cc,0,sizeof cc);
		cnt=0;
		for(int j=b[i].r; j>=b[i].l; j--) {
			++cnt;
			b[i].suf[cnt]=b[i].suf[cnt-1]+sum(a[j]-1);
			add(a[j],1);
		}
		memset(cc,0,sizeof cc);
	}
	for(int j=1; j<=bsize; j++)
		for(int i=n-1; i>=1; i--)
			c[j][i]+=c[j][i+1];
	for(int j=1; j<=bsize; j++)
		for(int i=1; i<=n; i++)
			c[j][i]+=c[j-1][i];
	for(int i=1;i<=bsize;i++){
		for(int j=i+1;j<=bsize;j++){
			int delta=0;
			for(int k=b[j].l; k<=b[j].r; k++) delta+=c[j-1][a[k]]-c[i-1][a[k]];
			ans[i][j]+=ans[i][j-1]+delta+ans[j][j];
		}
	}
	while(m--) {
		int l=read()^lastans,r=read()^lastans ;
		if(l>=r){
			printf("0\n");
			lastans=0;
			continue;
		}
		if(id[l]==id[r]) {
			lastans=tt1=tt2=0;
			for(int i=1; i<=b[id[l]].cnt; i++) {
				if(b[id[l]].k[i].second<l) t1[++tt1]=b[id[l]].k[i].first;
				else if(b[id[l]].k[i].second>=l&&b[id[l]].k[i].second<=r) t2[++tt2]=b[id[l]].k[i].first;
			}
			int cnt1=1,cnt2=1,tmp=0;
			while(cnt1<=tt1&&cnt2<=tt2) {
				if(t1[cnt1]>t2[cnt2]) tmp+=(tt1-cnt1+1),cnt2++;
				else cnt1++;
			}
			lastans=b[id[l]].pre[r-b[id[l]].l+1]-b[id[l]].pre[l-b[id[l]].l]-tmp;
			printf("%lld\n",lastans);
		} else {
			lastans=0;
			lastans+=ans[id[l]+1][id[r]-1];
			lastans+=b[id[l]].suf[b[id[l]].r-l+1]+b[id[r]].pre[r-b[id[r]].l+1];
			for(int i=l; i<=b[id[l]].r; i++) lastans+=(b[id[r]-1].r-b[id[l]+1].l+1)-(c[id[r]-1][a[i]]-c[id[l]][a[i]]);
			for(int i=b[id[r]].l; i<=r; i++) lastans+=c[id[r]-1][a[i]]-c[id[l]][a[i]];
			tt1=tt2=0;
			for(int i=1; i<=b[id[l]].cnt; i++)
				if(b[id[l]].k[i].second>=l) t1[++tt1]=b[id[l]].k[i].first;
			for(int i=1; i<=b[id[r]].cnt; i++)
				if(b[id[r]].k[i].second<=r) t2[++tt2]=b[id[r]].k[i].first;
			int cnt1=1,cnt2=1;
			while(cnt1<=tt1&&cnt2<=tt2) {
				if(t1[cnt1]>t2[cnt2]) lastans+=(tt1-cnt1+1),cnt2++;
				else cnt1++;
			}
			printf("%lld\n",lastans);
		}
	}
	return 0;
}