Given a sequence of length $n$ as $a_1, a_2, \dots, a_n$.
There are a total of $m$ queries, each query specifies $l, r$, and requires finding the number of subarrays $[i, j]$ within the range $[l, r]$ such that $l \leq i \leq j \leq r$ and the number of distinct elements in the subarray $[i, j]$ is odd.
### Input
- The first line is an integer $n$.
- The next line contains $n$ integers representing the sequence $a_1, a_2, \dots, a_n$.
- The following 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 integer on a new line, which is the result.
### Constraints
- $n, m, a_i \leq 10^6$
- $1 \leq l \leq r \leq n$
### Example #1
#### 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
```
### Example #2
#### 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
```
```
