给定一个长度 $n$ 的序列 $a_1,\dots,a_n$。

共有 $m$ 次询问，每次询问给定 $l,r$，求区间 $[l,r]$ 中有多少 子区间 $[i,j]$ 满足 $l\le i\le j\le r$，且在区间 $[i,j]$ 内出现过的数的个数为奇数。

输入格式

第一行一个整数 $n$。

接下来一行 $n$ 个整数表示序列 $a_1,\dots,a_n$

接下来一行一个整数 $m$。

接下来 $m$ 行，每行两个整数 $l\;r$ 表示一个询问。

输出格式

对每个询问，输出一行，包含一个整数，表示答案。

样例数据

样例 1 输入

5
2 3 5 1 5
5
2 3
1 1
1 3
2 5
2 4

样例 1 输出

2
1
4
6
4

样例 2 输入

10
2 8 5 1 10 5 9 9 3 5
10
6 8
1 2
3 5
5 7
1 7
3 9
4 9
1 4
3 7
2 5

样例 2 输出

4
2
4
4
16
16
12
6
9
6

子任务

Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078

对于 $25\%$ 的数据，满足 $1\le n,m\le 10^2$。

对于 $50\%$ 的数据，满足 $1\le n,m\le 10^4$。

对于另外 $25\%$ 的数据，满足序列中出现过的数个数不超过 $100$。

对于 $100\%$ 的数据，满足 $1\le n\le 10^6$，$1\le m\le 10^6$，$1\le a_i\le n。$

对每个询问满足 $1\le l\le r\le n$。

以上所有数值为整数。