Problem Description

You are given a sequence $a_1,\dots,a_n$ of length $n$.

There are $m$ queries. In each query, given $l,r$, find how many subintervals $[i,j]$ in the interval $[l,r]$ satisfy $l\le i\le j\le r$, and the number of distinct values that have appeared in $[i,j]$ is odd.

Input Format

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\;r$, representing a query.

Output Format

For each query, output one line containing one integer, which is the answer.

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

2
1
4
6
4

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

4
2
4
4
16
16
12
6
9
6

Hint

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

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

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

For the other $25\%$ of the testdata, the number of distinct values that appear in the sequence does not exceed $100$.

For $100\%$ of the testdata, $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.

Translated by ChatGPT 5