#include<bits/stdc++.h>
#define int long long
//#define int unsigned long long
#define PII pair<int,int>
using namespace std;
char *t1,*t2,buf[100000];
#define nc() (t1==t2 && (t2=(t1=buf)+fread(buf,1,100000,stdin),t1==t2)?EOF:*t1++)
inline int read() {
	int x=0,f=1;
	char ch=nc();
	while(ch<48||ch>57) {
		if(ch=='-')
			f=-1;
		ch=nc();
	}
	while(ch>=48&&ch<=57)
		x=x*10+ch-48,ch=nc();
	return x*f;
}
void write(int x) {
	if(x<0)
		putchar('-'),x=-x;
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
	return;
}
const int N=1e5+100;
const int BL=sqrt(N)+100;
PII p[N];
int n,m,blocksize,blockcnt,a[N],c[N],to[N],id[N];
int p1[BL],p2[BL],pre[BL][BL],suf[BL][BL],cnt[BL][N],ans[BL][BL],L[BL],R[BL];
inline void add(int x,int v) {
	for(int i=x; i<=n; i+=i&-i)c[i]+=v;
	return;
}
inline int sum(int x) {
	int s=0;
	for(int i=x; i; i-=i&-i)s+=c[i];
	return s;
}
inline int query(int l,int r) {
	if(l>r||l==r)return 0;
	if(id[l]==id[r]) {
		int sum=pre[id[l]][r-L[id[l]]+1]-pre[id[l]][l-L[id[l]]];
		int cnt1=0,cnt2=0;
		for(int i=L[id[l]]; i<=R[id[l]]; ++i) {
			if(p[i].second<l)p1[++cnt1]=p[i].first;
			if(p[i].second>=l&&p[i].second<=r)p2[++cnt2]=p[i].first;
		}
		for(int i=1,j=0; i<=cnt1; ++i) {
			while(j+1<=cnt2&&p2[j+1]<=p1[i])++j;
			sum-=j;
		}
		return sum;
	}
	int sum=0;
	sum+=suf[id[l]][R[id[l]]-l+1];
	sum+=pre[id[r]][r-L[id[r]]+1];
	sum+=ans[id[l]+1][id[r]-1];
	int cnt1=0,cnt2=0;
	for(int i=L[id[l]]; i<=R[id[l]]; ++i)if(p[i].second>=l)p1[++cnt1]=p[i].first;
	for(int i=L[id[r]]; i<=R[id[r]]; ++i)if(p[i].second<=r)p2[++cnt2]=p[i].first;
	if(id[l]+1<id[r]) {
		for(int i=1; i<=cnt1; ++i)sum+=R[id[r]-1]-L[id[l]+1]+1-(cnt[id[r]-1][p1[i]]-cnt[id[l]][p1[i]]);
		for(int i=1; i<=cnt2; ++i)sum+=cnt[id[r]-1][p2[i]]-cnt[id[l]][p2[i]];
	}
	for(int i=1,j=0; i<=cnt1; ++i) {
		while(j+1<=cnt2&&p2[j+1]<=p1[i])++j;
		sum+=j;
	}
	return sum;
}
signed main() {
	n=read(),m=read();
	for(int i=1; i<=n; ++i)a[i]=read(),p[i]= {a[i],i};
	blocksize=sqrt(n);
	blockcnt=ceil(n*1.0/blocksize);
	for(int i=1; i<=blockcnt; ++i) {
		L[i]=R[i-1]+1,R[i]=min(n,L[i]+blocksize-1);
		for(int j=L[i]; j<=R[i]; ++j)
			id[j]=i,to[a[j]]=i;
	}
	for(int i=1; i<=blockcnt; ++i)sort(p+L[i],p+1+R[i]);
	for(int i=1; i<=blockcnt; ++i) {
		for(int j=L[i]; j<=R[i]; ++j) {
			pre[i][j-L[i]+1]=pre[i][j-L[i]]+sum(n)-sum(a[j]);
			add(a[j],1);
		}
		for(int j=L[i]; j<=R[i]; ++j)add(a[j],-1);
	}
	for(int i=1; i<=blockcnt; ++i) {
		for(int j=R[i]; j>=L[i]; --j) {
			suf[i][R[i]-j+1]=suf[i][R[i]-j]+sum(a[j]-1);
			add(a[j],1);
		}
		for(int j=L[i]; j<=R[i]; ++j)add(a[j],-1);
	}
	for(int j=n; j; --j) {
		int buff=0;
		for(int i=1; i<=blockcnt; ++i) {
			if(to[j]==i)buff=1;
			cnt[i][j]=cnt[i][j+1]+buff;
		}
	}
	for(int i=1; i<=blockcnt; ++i)
		for(int j=i; j<=blockcnt; ++j) {
			int buff=pre[j][R[j]-L[j]+1];
			for(int k=L[j]; k<=R[j]; ++k)
				buff+=cnt[j-1][a[k]]-cnt[i-1][a[k]];
			ans[i][j]=ans[i][j-1]+buff;
		}
	int ans=0;
	while(m--) {
		int l=read()^ans,r=read()^ans;
		write(ans=query(l,r));
		putchar('\n');
	}
	return 0;
}//

评测40pts $Link$