#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
const short SqrtN = 359,SIZE = 1 << 14;
inline char gc(){
    static char buf[SIZE],*t1 = buf,*t2 = buf;
    return t1 == t2 && (t2 = (t1 = buf) + fread(buf,1,SIZE,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;
struct node{
    int num,id;
} a[N],tmp[N];
bool cmp(const node x,const node n){
	return x.num < n.num;
}
short block_cnt,block_len;
struct block{
	int l,r;
} b[SqrtN];
short belong[N];
int rk[SqrtN][SqrtN];//rk[i][j]：第i块排名为j的数 
short p[N][SqrtN];//p[i][j]：[b[bel[i]].l,i]这一段小于等于此块排名为j的数的个数 
int pre[SqrtN][N];//pre[i][j]：前i块中小于等于j的数的个数 
short rk2[SqrtN][N];//rk2[i][j]：第i块中小于等于j的数的个数（小于等于j的数的最大排名） 
long long ans1[SqrtN][SqrtN][SqrtN];//ans1[i][j][k]：第i块排名前k的数与前j块的数产生的顺序对个数 
int ans2[SqrtN][SqrtN][SqrtN];//ans2[i][j][k]：第i块内从排名j至排名k的顺序对数 
int query1(const int l,const int r){//块内查询 
	const short pos = belong[l];
	int ret = 0;
	for(int i = l;i <= r;i++){
		ret += p[i][rk2[pos][a[i].num - 1]];
		if(l != b[pos].l)
			ret -= p[l - 1][rk2[pos][a[i].num - 1]];
	}
	return ret;
}
int tmp1[N];short top1;
int tmp2[N];short top2;
long long query2(const int l,const int r){//跨块查询 
	const short 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 = 0;

	//散块内部
	//左散块内部 
	for(int i = l;i <= l_r;i++){
		ret += p[i][rk2[pos_l][a[i].num - 1]];
		if(l != l_l)
			ret -= p[l - 1][rk2[pos_l][a[i].num - 1]];
	}
	//右散块内部
	for(int i = r_l;i <= r;i++)
		ret += p[i][rk2[pos_r][a[i].num - 1]];

	//散块对散块
	top1 = top2 = 0;
	for(int i = l_l;i <= l_r;i++)
		if(tmp[i].id >= l)
			tmp1[++top1] = tmp[i].num;
	for(int i = r_l;i <= r_r;i++)
		if(tmp[i].id <= r)
			tmp2[++top2] = tmp[i].num;
	short 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)
			ret += (pre[pos_r - 1][n] - pre[pos_r - 1][tmp[i].num]) - (pre[pos_l][n] - pre[pos_l][tmp[i].num]);
	//右散块对整块 
	for(int i = r_l;i <= r_r;i++)
		if(tmp[i].id <= r)
			ret += pre[pos_r - 1][tmp[i].num] - pre[pos_l][tmp[i].num];

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

	//整块对整块
	for(short i = pos_l + 1;i <= pos_r - 1;i++)
		ret += ans1[i][i - 1][rk2[i][n]] - ans1[i][pos_l][rk2[i][n]];
	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};


	//建分块 
    block_len = 280;
    block_cnt = (n + block_len - 1) / block_len;
    for(short 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(short i = 1;i <= block_cnt;i++)
        for(int j = b[i].l;j <= b[i].r;j++)
            belong[j] = i;


	//预处理 


	//块内排序 
	for(short 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(short i = 1;i <= block_cnt;i++){
		const int l = b[i].l,r = b[i].r;
		for(int j = l;j <= r;j++)
			rk[i][j - l + 1] = tmp[j].num;
	}

	//预处理p 
	for(short i = 1;i <= block_cnt;i++){
		const int l = b[i].l,r = b[i].r;
		const short len = r - l + 1;
		for(int j = l;j <= r;j++)
			p[tmp[j].id][j - l + 1] = 1;
		for(int j = l;j <= r;j++){
			for(short k = 1;k <= len;k++){
				if(j > 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(short 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(short 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(short i = 1;i <= block_cnt;i++){
		const short len = b[i].r - b[i].l + 1;
		for(short j = 1;j < i;j++)
			for(short k = 1;k <= len;k++)
				ans1[i][j][k] = ans1[i][j][k - 1] + pre[j][rk[i][k]];
	}

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


	long long ans = 0;
	while(m--){
		const int l = read() ^ ans,r = read() ^ ans;
		int len = r - l + 1;
		if(belong[l] == belong[r])
			ans = ((1ll * len * (len - 1)) >> 1) - query1(l,r);
		else
			ans = ((1ll * len * (len - 1)) >> 1) - query2(l,r);
		cout << ans << '\n';
	}
	return 0; 
}