#include <cstdio>

 #include <algorithm>

 #include <cmath>

 #include <cstring>

 using namespace std;

 #define isdigit(x) (x <= '9' && x >= '0')

 #define lowbit(x) (x & (-x))

 const int N = 5e4 + ;

 const int M = ;

 struct s {

     int u, v;

     inline bool operator < (const s &o) const {

         return u < o.u;

     }

 } a[N];

 inline void read(int &ans) {

     ans = ;

     static char buf = getchar();

     for (; !isdigit(buf); buf = getchar());

     for (; isdigit(buf); buf = getchar())

         ans = ans *  + buf - '';

 }

 int n, cnt, maxn, sz;

 int s[M][N], f[M][N], c[N], d[N], b[N];

 inline void add(int x, int a) {

     while (x <= maxn) {

         c[x] += a;

         x += lowbit(x);

     }

 }

 inline int query(int x) {

     int ans = ;

     while (x > ) {

         ans += c[x];

         x -= lowbit(x);

     }

     return ans;

 }

 inline void work(int x) {

     int h = (x - ) * sz + ;

     int t = x * sz;

     for (int i = h; i <= n; i++)

         add(d[i], ), f[x][i] = f[x][i - ] + i - h +  - query(d[i]);

     memset(c, , sizeof(c));

     for (int i = h; i <= t; i++)    s[x][d[i]]++;

     for (int i = ; i <= maxn; i++)    s[x][i] += s[x][i - ];

     for (int i = ; i <= maxn; i++)    s[x][i] += s[x - ][i];

 }

 int main() {

     read(n);

     sz = sqrt(n);

     for (int i = ; i <= n; i++) {

         read(a[i].u); a[i].v = i;

         b[i] = (i - ) / sz + ;

     }

     cnt = b[n];

     sort(a + , a + n + );

     int last = ; d[a[].v] = ;

     for (int i = ; i <= n; i++) {

         if (a[i].u == a[i - ].u)    d[a[i].v] = last;

         else    d[a[i].v] = ++last;

     }

     maxn = last;

     for (int i = ; i <= cnt; i++)

         work(i);

     int m; read(m);

     int ans = ;

     while (m--) {

         int l, r;

         read(l); read(r);

         l = l ^ ans; r = r ^ ans;

         ans = ;

         if (l > r)    swap(l, r);

         if (b[l] == b[r]) {

             for (int i = l; i <= r; i++)

                 add(d[i], ), ans += i - l +  - query(d[i]);

             for (int i = l; i <= r; i++)    add(d[i], -);

         }

         else {

             ans = f[b[l] + ][r];

             for (int i = (b[r] - ) * sz + ; i <= r; i++)    add(d[i], );

             for (int i = b[l] * sz; i >= l; i--)

                 add(d[i], ), ans += query(d[i] - ) + s[b[r] - ][d[i] - ] - s[b[l]][d[i] - ];

             for (int i = (b[r] - ) * sz + ; i <= r; i++)    add(d[i], -);

             for (int i = l; i <= b[l] * sz; i++)    add(d[i], -);

         }

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

     }

 }