rt

#include<bits/stdc++.h>
using namespace std;
const short cl=240,kj=420;
inline long long qread()
{
	register long long a=0,f=1;register char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){a=(a<<1)+(a<<3)+(ch^48);ch=getchar();}
	return a*f; 
}
int n,m,a[100010],b[100010],c[100010],st[kj],ed[kj],pos[100010],f[kj][100010],ff[kj][100010],gq[100010],gh[100010],nl,nr;
long long lastans=0,t[kj][kj];
/*
a[]:原排列 
b[]:分块排序后的排列
cl:块长 
c[i]:i的所属块
st[i]:第i块起点
ed[i]:第i块终点 
gq[i]:i到第i块的块首中逆序对数
gh[i]:i到第i块的块尾中逆序对数
t[i][j]:第i块对第j块贡献，后前缀和为第i块对i+1到j块的贡献
ff[i]为[j]:1到i块中比j小的数 ,f[i][j]:为第i块中比j大的数，后前缀和为1到i块中比j大的数 
pos[i]:i在原排列中的位置 
*/
inline long long solve()
{
	register long long ans=0;
	if(c[nl]==c[nr])
	{
		ans+=gq[nr]-gq[nl-1];
		register int rr=0;
		for(register int i=st[c[nl]];i<=ed[c[nl]];++i)
		{
			if(pos[b[i]]>=nl&&pos[b[i]]<=nr)rr++;
			if(pos[b[i]]<nl)ans-=rr;
		}
	}
	else
	{
		register int bb=ed[c[nl]]-st[c[nl]]+1+ed[c[nr]]-st[c[nr]]+1,zp=st[c[nl]],yp=st[c[nr]],rr=0;
		while(bb--)
		{
			if(b[zp]>=b[yp]&&yp<=ed[c[nr]])
			{
				pos[b[yp]]<=nr?++rr:0;
				++yp;
			}
			else if(zp<=ed[c[nl]])
			{
				pos[b[zp]]>=nl?ans+=rr:0;
				++zp;
			}
			else ++yp;
		}
		register int nrr=c[nr]-1,nll=c[nl]+1;
		ans+=t[nll][nrr];
		ans+=gh[nl];
		ans+=gq[nr];
		for(register int i=nl;i<=ed[c[nl]];++i)ans+=ff[nrr][a[i]]-ff[c[nl]][a[i]];
		for(register int i=st[c[nr]];i<=nr;++i)ans+=f[nrr][a[i]]-f[c[nl]][a[i]];
	}
	return ans;
}
int main()
{
	n=qread();m=qread();
	for(register int i=1;i<=n;++i)
	{
		b[i]=a[i]=qread();
		pos[a[i]]=i;
		c[i]=(i-1)/cl+1;
		ed[c[i]]=i;
	}
	for(register int i=n;i>=1;--i)st[c[i]]=i;
	for(register int i=1;i<=c[n];++i)
	{
		for(register int j=st[i]+1,jj;j<=ed[i];++j)
		{
			jj=ed[i]-j+st[i];
			gq[j]=gq[j-1];gh[jj]=gh[jj+1];
			for(register int k=st[i],kk;k<j;++k)
			{
				kk=ed[i]-k+st[i];
				gq[j]+=(a[k]>a[j]);
				gh[jj]+=(a[kk]<a[jj]);
			}
		}
	}
	for(register int i=1;i<=c[n];++i)
	{
		sort(b+st[i],b+ed[i]+1);
		t[i][i]=gh[st[i]];
		for(register int j=1;j<=n;++j)
		{
			f[i][j]=f[i][j-1]+(pos[j-1]>=st[i]&&pos[j-1]<=ed[i]);
			ff[i][j]=ff[i-1][j]+f[i][j];
		}
	}
	for(register int i=2,j;i<=c[n];++i)
	{
		j=c[n]-i+1;
		for(register int l=1,r;l<=j;++l)
		{
			r=l+i-1;
			t[l][r]=t[l+1][r]+t[l][r-1]-t[l+1][r-1];
			for(register int k=st[l];k<=ed[l];++k)t[l][r]+=f[r][a[k]];
		}
	}
	for(register int i=1;i<=c[n];++i)
	{
		for(register int j=1;j<=n;++j)
		{
			f[i][j]=ed[i]-ff[i][j];
		}
	}
	for(register int i=1;i<=m;++i)
	{
		nl=qread()^lastans;
		nr=qread()^lastans;
		lastans=solve();
		cout<<lastans<<endl;
	}
	return 0;
}