Pang 教授得到了一个固定的序列 $a_1, \dots, a_n$ 以及 $m$ 次询问。

每个询问由两个整数 $l$ 和 $r$ 指定，满足 $1 \le l \le r \le n$。对于每个询问，你需要回答满足 $l \le i \le j \le r$ 且 $a_i, \dots, a_j$ 中不同整数的个数为奇数的整数对 $(i, j)$ 的数量。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 5 \times 10^5$)。

第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($1 \le a_i \le n$，对于所有 $1 \le i \le n$)，整数之间用空格分隔。

第三行包含一个整数 $m$ ($1 \le m \le 5 \times 10^5$)。

接下来的 $m$ 行，每行包含两个整数 $l$ 和 $r$ ($1 \le l \le r \le n$)，用空格分隔，表示一次询问。

输出格式

对于每个询问，输出一行，包含该询问的答案。

样例

输入 1

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

输出 1

10
3
4
6
1

输入 2

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

输出 2

2
1
4
6
4

输入 3

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

输出 3

4
2
4
4
16
16
12
6
9
6