垃圾实现垃圾常数

//你很牛吗？放下你的身段！
#include <bits/stdc++.h>
#define Maxn 100005
#define Nep(i, l, r) for(register int i = l, _ = r; i != _; ++ i)
#define Rep(i, l, r) for(register int i = l, _ = r; i <= _; ++ i)
#define rep(i, l, r) for(register int i = l, _ = r; i < _; ++ i)
#define Lep(i, l, r) for(register int i = l, _ = r; i >= _; -- i)
#define lep(i, l, r) for(register int i = l, _ = r; i > _; -- i)
#define ll long long
#define ull unsigned long long
//#define int long long

struct IO {
	static const int S=1<<21;
	char buf[S],*p1,*p2;
	int st[105],Top;
	~IO() {
		clear();
	}
	inline void clear() {
		fwrite(buf,1,Top,stdout);
		Top=0;
	}
	inline void pc(const char c) {
		Top==S&&(clear(),0);
		buf[Top++]=c;
	}
	inline char gc() {
		return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
	}
	inline IO&operator >> (char&x) {
		while(x=gc(),x==' '||x=='\n'||x=='r');
		return *this;
	}
	template<typename T>inline IO&operator >> (T&x) {
		x=0;
		bool f=0;
		char ch=gc();
		while(ch<'0'||ch>'9') {
			if(ch=='-') f^=1;
			ch=gc();
		}
		while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
		f?x=-x:0;
		return *this;
	}
	inline IO&operator << (const char c) {
		pc(c);
		return *this;
	}
	template<typename T>inline IO&operator << (T x) {
		if(x<0) pc('-'),x=-x;
		do {
			st[++st[0]]=x%10,x/=10;
		} while(x);
		while(st[0]) pc('0'+st[st[0]--]);
		return *this;
	}
} fin,fout;


const int B = 500, Maxt = Maxn / B + 5;
int a[Maxn], bcnt, n, m;
int bel[Maxn];
int L[Maxt], R[Maxt];
ll res[Maxt][Maxt];
int da[Maxn];
int ov[Maxn]; 
int dov[Maxn];
ll pre[Maxn][Maxt];
ll d[Maxn];
int u[Maxn][B + 5];
int st[Maxn], sp[Maxt];

signed main() { 
	fin >> n >> m;
	Rep(i, 1, n) bel[i] = (i - 1) / B + 1;
	Rep(i, 1, bel[n]) L[i] = R[i - 1] + 1, R[i] = L[i] + B - 1; 
	bcnt = bel[n], R[bcnt] = n;
	Rep(i, 1, n) fin >> a[i], ov[i] = a[i], da[a[i]] = i; 
	Rep(b, 1, bcnt) std :: sort(ov + L[b], ov + R[b] + 1);	
	Rep(i, 1, n) dov[i] = da[ov[i]]; 
	
	
	Rep(i, 1, n) {
		Rep(x, a[i], R[bel[a[i]]]) st[x] ++;
		Rep(b, bel[a[i]], bcnt) sp[b] ++;
		d[i] = st[a[i] - 1] + sp[bel[a[i] - 1] - 1];
		
		if(i == R[bel[i]]) Rep(x, 1, n) 
			pre[x][bel[i]] = st[a[x] - 1] + sp[bel[a[x] - 1] - 1];
	}
	
	
	Rep(b, 1, bcnt) Rep(i, L[b], R[b]) res[b][b] += i - L[b] - d[i] + pre[i][b - 1];
	Rep(b, 1, bcnt) Rep(i, 1, n) pre[i][b] += pre[i - 1][b];
	Rep(i, 1, n) d[i] += d[i - 1];
	
	rep(r, 1, B) Rep(l, 1, n) {
		if(bel[l + r] != bel[l]) continue; 
		u[l][r] = u[l + 1][r - 1] + u[l][r - 1] + (a[l] > a[l + r]);
		if(r > 2) u[l][r] -= u[l + 1][r - 2];
	}
	
	Lep(l, bcnt, 1) Rep(r, l + 1, bcnt) {
		res[l][r] += res[l + 1][r] + res[l][l];
		res[l][r] += pre[R[l]][r] - pre[L[l] - 1][r];
		res[l][r] -= pre[R[l]][l] - pre[L[l] - 1][l];
	}
	
	ll las = 0;
	
	Rep(q, 1, m) {
		ll ql, qr; fin >> ql >> qr;
		const int l = ql ^ las, r = qr ^ las;
		
		if(bel[l] == bel[r]) {
			fout << u[l][r - l] << '\n', las = u[l][r - l];
			continue;
		}	
		
		const int bL = bel[l], bR = bel[r];	
		ll ans = res[bL + 1][bR - 1];
		const int len = r - L[bR] + 2 + R[bL] - l;
		int lc = L[bL], rc = L[bR], rcnt = 0;
		
		
		Rep(i, 1, len) {
			while(dov[lc] < l && lc <= R[bL]) lc ++;
			while(dov[rc] > r && rc <= R[bR]) rc ++; 
			if(lc > R[bL]) break;
			
			if(rc > R[bR]) {
				ans += 1LL * (len - i + 1) * rcnt;
				break;
			}
			
			if(ov[lc] < ov[rc]) lc ++, ans += rcnt; 
			else rc ++, rcnt ++; 
		} 
		
		ans += pre[R[bL]][bR - 1] - pre[l - 1][bR - 1];
		ans -= d[R[bL]] - d[l - 1];
		ans += 1LL * (L[bR] + r) * (r - L[bR] + 1) / 2;
		ans -= 1LL * (R[bL] + 1) * (r - L[bR] + 1);
		ans -= d[r] - d[L[bR] - 1];
		ans += pre[r][bL] - pre[L[bR] - 1][bL];
		
		fout << ans << '\n', las = ans;
	} 
	
	
	return 0;
}