已知 $n\leq 1000$ 时可以拍上，提交会 RE，#define int long long 后会变为 MLE。悬赏两个关注，不胜感激！

#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int B=350;
const int N=100000+10;
const int BLO=N/B+5;
const int maxn=2e5+10;
const int mod=1e9+7;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
int n,m,a[N],b[N],blo,lft[BLO],rht[BLO],bel[N],tr[N],L[N],R[N],f[BLO][B+5][B+5],iv[N];
long long ans[BLO][BLO],las;int now[N],g[N][BLO];
inline int query(int x){int res=0;for(;x;x-=x&(-x))res+=tr[x];return res;}
inline void add(int x){for(;x<=n;x+=x&(-x))tr[x]++;}
inline void clear(int x){for(;x<=n;x+=x&(-x))tr[x]=0;}
inline int merge(int b1,int b2,int l,int r){
	int p1=lft[b1],p2=lft[b2],e1=rht[b1],e2=rht[b2],cnt=0,res=0;
	while(p1<=e1){
		if(p2>e2||b[p2]>b[p1]){
			if(iv[b[p1]]>=l)res+=cnt;
			p1++;continue;
		}else{
			if(iv[b[p2]]<=r)cnt++;
			p2++;continue;
		}
	}return res;
}
inline long long Query(int l,int r){
	if(bel[l]==bel[r])return (long long)f[bel[l]][l-lft[bel[l]]][r-lft[bel[l]]];
	long long res=0ll+R[l]+L[r]+merge(bel[l],bel[r],l,r);
	res+=ans[bel[l]+1][bel[r]-1];
	for(int i=l;i<=rht[bel[l]];i++)
		res+=0ll+g[i][bel[r]-1]-g[i][bel[l]];
	for(int i=lft[bel[r]];i<=r;i++)
		res+=0ll+rht[bel[r]-1]-rht[bel[l]]-(g[i][bel[r]-1]-g[i][bel[l]]);
	return res;
}
int main(){
	freopen("P5046.in","r",stdin);
	freopen("P5046.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++)a[i]=b[i]=read();
	for(int i=1;i<=n;i++)iv[a[i]]=i;
	for(;;){
		lft[++blo]=rht[blo-1]+1;
		rht[blo]=min(lft[blo]+B-1,n);
		for(int j=lft[blo];j<=rht[blo];j++)bel[j]=blo;
		sort(b+lft[blo],b+rht[blo]+1);
		for(int j=lft[blo];j<=rht[blo];j++)
			ans[blo][blo]+=query(n-a[j]+1),add(n-a[j]+1),L[j]=ans[blo][blo];
		for(int j=lft[blo];j<=rht[blo];j++)clear(n-a[j]+1);
		for(int j=rht[blo];j>=lft[blo];j--)R[j]+=R[j+1]+query(a[j]),add(a[j]);
		for(int j=lft[blo];j<=rht[blo];j++)clear(a[j]);
		for(int len=2,k,jj,kk;len<=rht[blo]-lft[blo]+1;len++)
			for(int j=lft[blo];j+len-1<=rht[blo];j++){
				k=j+len-1,jj=j-lft[blo],kk=k-lft[blo];
				f[blo][jj][kk]=f[blo][jj][kk-1]+f[blo][jj+1][kk]-f[blo][jj+1][kk-1]+(a[j]>a[k]);
			}
		for(int j=lft[blo];j<=rht[blo];j++)now[a[j]]=1;
		for(int j=1;j<=n;j++)now[j]+=now[j-1];
		for(int j=1;j<=n;j++)g[j][blo]=g[j][blo-1]+now[a[j]];
		for(int j=1;j<=n;j++)now[j]=0;
		if(rht[blo]==n)break;
	}
	for(int i=1;i<=blo;i++)
		for(int j=i+1;j<=blo;j++)
			ans[i][j]=merge(i,j,lft[i],rht[j]);
	for(int i=1;i<=blo;i++){
		long long sum=ans[i][i];
		for(int j=i-1;j>=1;j--)
			sum+=ans[j][i],ans[j][i]=ans[j][i-1]+sum;
	}
	for(int i=1;i<=m;i++){
		long long l,r;
		scanf("%lld%lld",&l,&r);
		l^=las,r^=las;
		if(l>r)swap(l,r);
		printf("%lld\n",las=Query(l,r));
	}
	return 0;
}