#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1,BLEN = 317,BCNT = N / BLEN + 1;
inline char gc(){
    static char buf[10000005],*t1 = buf,*t2 = buf;
    return t1 == t2 && (t2 = (t1 = buf) + fread(buf,1,1000000,stdin),t1 == t2) ? EOF : *t1++;
}
int read(){
	char c = gc();
	int x = 0;
	while(c < '0' || c > '9')
		c = gc();
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + c - 48;
		c = gc();
	}
	return x;
}
int n,m;
long long ans;
struct node{
    int num,id;
} a[N],tmp[N];
bool cmp(node x,node y){
	return x.num < y.num;
}
int block_cnt,block_len;
struct block{
	int l,r;
} b[BCNT];
int belong[N];
void build_block(){
    block_len = 316;
    block_cnt = (n + block_len - 1) / block_len;
    for(int i = 1;i <= block_cnt;i++){
        b[i].l = b[i - 1].r + 1;
        b[i].r = b[i].l + block_len - 1;
    }
    b[block_cnt].r = n;
    for(int i = 1;i <= block_cnt;i++)
        for(int j = b[i].l;j <= b[i].r;j++)
            belong[j] = i;
}
int rk[BCNT][BLEN];//rk[i][j]：第i块排名为j的数 
int p[N][BLEN];//p[i][j]：[b[bel[i]].l,i]这一段小于等于此块排名为j的数的个数 
int pre[BCNT][N];//pre[i][j]：前i块中小于等于j的数的个数 
short rk2[BCNT][N];//rk2[i][j]：第i块中小于等于j的数的个数（小于等于j的数的最大排名） 
long long ans1[BCNT][BCNT][BLEN];//ans1[i][j][k]：第i块排名前k的数与前j块的数产生的顺序对个数 
int ans2[BCNT][BLEN][BLEN];//ans2[i][j][k]：第i块内从排名j至排名k的顺序对数 
void init(){
	for(int i = 1;i <= block_cnt;i++){
		const int l = b[i].l,r = b[i].r;
		sort(tmp + l,tmp + r + 1,cmp);
	}

	//预处理rk 
	for(int i = 1;i <= block_cnt;i++)
		for(int j = b[i].l;j <= b[i].r;j++)
			rk[i][j - b[i].l + 1] = tmp[j].num;

	//预处理p 
	for(int i = 1;i <= block_cnt;i++){
		for(int j = b[i].l;j <= b[i].r;j++)
			p[tmp[j].id][j - b[i].l + 1] = 1;
		for(int j = b[i].l;j <= b[i].r;j++){
			for(int k = 1;k <= b[i].r - b[i].l + 1;k++){
				if(j > b[i].l)
					p[j][k] += p[j][k - 1] + p[j - 1][k] - p[j - 1][k - 1];
				else
					p[j][k] += p[j][k - 1];
			}
		}
	}

	//预处理pre
	for(int i = 1;i <= block_cnt;i++){
		for(int j = b[i].l;j <= b[i].r;j++)
			pre[i][a[j].num] = 1;
		for(int j = 1;j <= n;j++)
			pre[i][j] = pre[i][j] + pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1];
	}

	//预处理rk2
	for(int i = 1;i <= block_cnt;i++)
		for(int j = 1;j <= n;j++)
			rk2[i][j] = pre[i][j] - pre[i - 1][j];

	//预处理ans1
	for(int i = 1;i <= block_cnt;i++)
		for(int j = 1;j < i;j++)
			for(int k = 1;k <= b[i].r - b[i].l + 1;k++)
				ans1[i][j][k] = ans1[i][j][k - 1] + pre[j][rk[i][k]];

	//预处理ans2
	for(int i = 1;i <= block_cnt;i++)
		for(int j = 1;j < b[i].r - b[i].l + 1;j++)
			for(int k = j + 1;k <= b[i].r - b[i].l + 1;k++)
				ans2[i][j][k] = ans2[i][j][k - 1] + p[tmp[b[i].l + k - 1].id][k - 1] - p[tmp[b[i].l + k - 1].id][j - 1];
}
int query1(const int l,const int r,const int x,const int y){//块内查询 
	const int pos = belong[l];
	int ret = 0;
	for(int i = l;i <= r;i++)
		if(a[i].num >= x && a[i].num <= y){
			ret += p[i][rk2[pos][a[i].num - 1]] - p[i][rk2[pos][x - 1]];
			if(l != b[pos].l)
				ret -= p[l - 1][rk2[pos][a[i].num - 1]] - p[l - 1][rk2[pos][x - 1]];
		}
	return ret;
}
int tmp1[N],top1;
int tmp2[N],top2;
long long query2(const int l,const int r,const int x,const int y){//跨块查询 
	const int pos_l = belong[l],pos_r = belong[r];
	const int l_l = b[pos_l].l,l_r = b[pos_l].r;
	const int r_l = b[pos_r].l,r_r = b[pos_r].r;
	long long ret = query1(l,b[pos_l].r,x,y) + query1(b[pos_r].l,r,x,y);//散块内部

	//散块对散块
	top1 = top2 = 0;
	for(int i = l_l;i <= l_r;i++)
		if(tmp[i].id >= l && tmp[i].num >= x && tmp[i].num <= y)
			tmp1[++top1] = tmp[i].num;
	for(int i = r_l;i <= r_r;i++)
		if(tmp[i].id <= r && tmp[i].num >= x && tmp[i].num <= y)
			tmp2[++top2] = tmp[i].num;
	int i = 1,j = 1;
	while(i <= top1 && j <= top2){
		if(tmp1[i] < tmp2[j]){
			i++;
			ret += top2 - j + 1;
		}
		else
			j++;
	}

	//整块对散块
	//左散块对整块 
	for(int i = l_l;i <= l_r;i++)
		if(tmp[i].id >= l && tmp[i].num >= x && tmp[i].num <= y)
			ret += (pre[pos_r - 1][y] - pre[pos_r - 1][tmp[i].num]) - (pre[pos_l][y] - pre[pos_l][tmp[i].num]);
	//右散块对整块 
	for(int i = r_l;i <= r_r;i++)
		if(tmp[i].id <= r && tmp[i].num >= x && tmp[i].num <= y)
			ret += (pre[pos_r - 1][tmp[i].num] - pre[pos_r - 1][x - 1]) - (pre[pos_l][tmp[i].num] - pre[pos_l][x - 1]);

	//整块内部 
	for(int i = pos_l + 1;i <= pos_r - 1;i++)
		ret += ans2[i][rk2[i][x - 1] + 1][rk2[i][y]];

	//整块对整块
	for(int i = pos_l + 1;i <= pos_r - 1;i++)
		ret += (ans1[i][i - 1][rk2[i][y]] - ans1[i][i - 1][rk2[i][x - 1]]) - (ans1[i][pos_l][rk2[i][y]] - ans1[i][pos_l][rk2[i][x - 1]]);
	//最后要减去[1,x - 1]（前半段值域）对[x,y]（后半段值域） 的贡献
	int temp = 0;
	for(int i = pos_l + 1;i <= pos_r - 1;i++){
		ret -= 1ll * temp * (rk2[i][y] - rk2[i][x - 1]);
		temp += rk2[i][x - 1];
	}
	return ret;
}
signed main(){ 
	ios::sync_with_stdio(false);
	cout.tie(0);
	n = read();m = read();
	for(int i = 1;i <= n;i++)
		tmp[i] = a[i] = (node){read(),i};
	build_block();
	init();
	while(m--){
		int x1 = read(),x2 = read();
		x1 ^= ans;x2 ^= ans;
		int len = x2 - x1 + 1;
		if(belong[x1] == belong[x2])
			ans = ((1ll * len * (len - 1)) >> 1) - query1(x1,x2,1,n);
		else
			ans = ((1ll * len * (len - 1)) >> 1) - query2(x1,x2,1,n);
		cout << ans << '\n';
	}
	return 0; 
}