#include<bits/stdc++.h>
using namespace std;
#define For(i, l, r) for(int i=(l);i<=(r);++i)
#define Rfor(i, r, l) for(int i=(r);i>=(l);--i)
#define O(x) cerr<<(#x)<<":"<<(x)<<endl
#define OO(x,y) cerr<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<endl
#define OOO(x,y,z) cerr<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<(#z)<<":"<<(z)<<endl
#define OOOO(x,y,z,f) cerr<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<(#z)<<":"<<(z)<<" "<<(#f)<<":"<<f<<endl
#define FENGE cerr<<"----------------------------------------------------------"<<endl
#define LO(a, l, r) {For(supervariable, l, r)cerr<<a[supervariable]<<" ";cerr<<"\n";}
#define FS(v,V,u,fa) for(int v:V[(u)])if(v!=(fa))
long long read(){long long x=0,t=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')t=-t;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return x*t;}
char getdig(){char ch=getchar();while(ch=='\n'||ch==' ')ch=getchar();return ch;}
constexpr int N=100000,B=316,NdB=N/B;
int bel(int x){return (x-1)/B+1;}
int n,bn;
int spos(int x){return (x-1)*B+1;}
int epos(int x){return x^bn?x*B:n;}
vector<pair<int,int> > sorted[NdB+5];
int skn[N+5][2];	//0:pre
long long zdz[NdB+5][NdB+5],g[NdB+5][NdB+5],ZDZ[NdB+5][NdB+5];
int sdz[NdB+5][N+5];
long long getAns(vector<pair<int,int> > &v1,vector<pair<int,int> > v2)
{
	vector<pair<int,int> > res;long long ans=0;
	int l1=0,l2=0;
	while(l1<v1.size()||l2<v2.size())
	{
		if(l1==v1.size())res.push_back(v2[l2++]),ans+=v1.size()-l1;
		else if(l2==v2.size())res.push_back(v1[l1++]);
		else if(v1[l1].first<=v2[l2].first)res.push_back(v1[l1++]);
		else res.push_back(v2[l2++]),ans+=v1.size()-l1;
	}
	v1=res;return ans;
}
int a[N+5];
void init()
{
	vector<pair<int,int> > V;
	For(i, 1, bn)
	{
		V.emplace_back(a[spos(i)],spos(i));
		For(j, spos(i)+1, epos(i))
		{
			skn[j][0]=skn[j-1][0];
			int k;
			for(k=V.size()-1;k>=0;--k)
				if(V[k].first>a[j])++skn[j][0];else break;
			V.insert(V.begin()+k+1, {a[j], j});
		}
		swap(sorted[i], V);
	}
	For(i, 1, bn)
	{
		V.emplace_back(a[epos(i)], epos(i));
		Rfor(j, epos(i)-1, spos(i))
		{
			skn[j][1]=skn[j+1][1];
			int k;
			for(k=0;k<V.size();++k)
				if(V[k].first<a[j])++skn[j][1];else break;
			V.insert(V.begin()+k, {a[j], j});
		}
		V.clear();
	}
	For(i, 1, n)++sdz[bel(i)][a[i]];
	For(i, 2, bn)
		For(j, 1, N)sdz[i][j]+=sdz[i-1][j];
	For(i, 1, bn)
		For(j, 1, N)sdz[i][j]+=sdz[i][j-1];	//1~i块内小于j的有多少数
	Rfor(i, bn, 1)
	{
		Rfor(j, i-1, 1)
		{
			g[j][i]=g[j+1][i];
			For(k, spos(j), epos(j))
				g[j][i] += sdz[i][a[k]] - sdz[i-1][a[k]];
		}
	}
	For(i, 1, bn)
	{
		zdz[i][i]=skn[epos(i)][0];
		For(j, i+1, bn)
		{
			zdz[i][j] = zdz[i][j-1] + skn[epos(j)][0] + g[i][j];
		}
	}
}
int main()
{
	int start=clock();
	freopen("in.in","r",stdin);
	freopen("std.out","w",stdout);	
	n=read();bn=ceil(1.0*n/B);int m=read();
	For(i, 1, n)a[i]=read();
	init();
	long long lastans=0;
	while(m--)
	{
		long long x=read()^lastans,y=read()^lastans;
		int l=bel(x),r=bel(y);
		if(l==r)
		{
			vector<pair<int,int> > v1,v2;assert(!v1.size());assert(!v2.size());
			for(auto [u,id]:sorted[l])
				if(id<x)v1.emplace_back(u,id);
				else if(id<=y)v2.emplace_back(u,id);
			printf("%lld\n", lastans = skn[y][0] - (x>spos(l))*skn[x-1][0] - getAns(v1, v2));
		}
		else
		{
			long long ans = zdz[l+1][r-1] + skn[x][1] + skn[y][0];
			For(i, x, epos(l)) ans += sdz[r-1][a[i]-1] - sdz[l][a[i]-1];
			For(i, spos(r), y) ans += (sdz[r-1][N] - sdz[l][N]) - (sdz[r-1][a[i]] - sdz[l][a[i]]);
			vector<pair<int,int> > v1,v2;
			assert(!v1.size());assert(!v2.size());
			for(auto [u,id]:sorted[l])
				if(id>=x)v1.emplace_back(u,id);
			for(auto [u,id]:sorted[r])
				if(id<=y)v2.emplace_back(u,id);
			ans += getAns(v1, v2);
			printf("%lld%c",lastans=ans,'\n');
		}
	}
	cerr<<1.0*(clock()-start)/CLOCKS_PER_SEC<<endl;
}