Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 50010

int a[MAXN];

//block

#define MAXB 240

int L[MAXB],R[MAXB],tot,belong[MAXN];

inline void build(int l,int r,int k)

{

	L[k] = l;R[k] = r;

	for(register int i = l;i <= r;++i)belong[i] = k;

	return;

}

//BIT

struct BIT

{

	int c[MAXN];

	pair<int,int> s[MAXN];

	int top;

	BIT(){memset(c,0,sizeof(c));top = 0;}

	inline int lowbit(int x){return x&(-x);}

	inline void add(int p,int k){s[++top] = make_pair(p,k);for(register int i = p;i <= n;i += lowbit(i))c[i] += k;return;}

	inline void dec(int p,int k){for(register int i = p;i <= n;i += lowbit(i))c[i] -= k;return;}

	inline int query(int p){int res = 0;for(register int i = p;i >= 1;i -= lowbit(i))res += c[i];return res;}

	inline void reset(){while(top > 0){dec(s[top].first,s[top].second);--top;}return;}

}l;

//discritise

int s[MAXN],cur = 0;

int p[MAXN];

bool cmp(int x,int y){return a[x] < a[y];}

int c[MAXB][MAXN],f[MAXB][MAXN];

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int main()

{

	n = read();

	for(register int i = 1;i <= n;++i)a[i] = read();

	tot = sqrt(n);

	for(register int i = 1;i <= tot;++i)build((i - 1) * tot + 1,i * tot,i);

	if(tot * tot < n){build(R[tot] + 1,n,tot + 1);++tot;}

	for(register int i = 1;i <= n;++i)s[i] = i;

	sort(s + 1,s + 1 + n,cmp);

	for(register int i = 1;i <= n;++i)

	{

		if(a[s[i]] == a[s[i - 1]])p[s[i]] = cur;

		else p[s[i]] = ++cur;

	}

	for(register int i = 1;i <= tot;++i)

	{

		for(register int j = L[i];j <= n;++j)

		{

			f[i][j] = f[i][j - 1] + l.query(cur) - l.query(p[j]);

			l.add(p[j],1);

		}

		l.reset();

	}

	for(register int i = 1;i <= tot;++i)

	{

		for(int j = L[i];j <= R[i];++j)++c[i][p[j]];

		for(int j = 1;j <= cur;++j)c[i][j] += c[i][j - 1];

		for(int j = 1;j <= cur;++j)c[i][j] += c[i - 1][j];

	}

	m = read();

	register int a,b;

	register int lastans = 0;

	for(register int i = 1;i <= m;++i)

	{

		a = read();b = read();a ^= lastans;b ^= lastans;

		register int ans = 0;

		if(belong[a] == belong[b])

		{

			for(register int k = a;k <= b;++k)

			{

				ans += l.query(cur) - l.query(p[k]);

				l.add(p[k],1);

			}

			l.reset();

		}

		else

		{

			ans = f[belong[a] + 1][b];

			for(register int k = L[belong[b]];k <= b;++k)l.add(p[k],1);

			for(register int k = R[belong[a]];k >= a;--k)

			{

				ans += c[belong[b] - 1][p[k] - 1] - c[belong[a]][p[k] - 1] + l.query(p[k] - 1);

				l.add(p[k],1);

			}

			l.reset();

		}

		printf("%d\n",(lastans = ans));

	}

	return 0;

}