Given a sequence $a_1, \dots, a_n$ of length $n$.

There are $m$ queries. Each query provides $l$ and $r$, and you need to find the number of subsegments $[i, j]$ such that $l \le i \le j \le r$, where the number of distinct elements appearing in the subsegment $[i, j]$ is odd.

Input

The first line contains an integer $n$.

The next line contains $n$ integers representing the sequence $a_1, \dots, a_n$.

The next line contains an integer $m$.

The next $m$ lines each contain two integers $l$ and $r$ representing a query.

Output

For each query, output a single line containing an integer representing the answer.

Examples

Input 1

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

Output 1

2
1
4
6
4

Input 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

Output 2

4
2
4
4
16
16
12
6
9
6

Subtasks

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078

For $25\%$ of the data, $1 \le n, m \le 10^2$.

For $50\%$ of the data, $1 \le n, m \le 10^4$.

For another $25\%$ of the data, the number of distinct elements appearing in the sequence does not exceed $100$.

For $100\%$ of the data, $1 \le n \le 10^6$, $1 \le m \le 10^6$, $1 \le a_i \le n$.

For each query, $1 \le l \le r \le n$.

All values above are integers.