31083번 - Prof. Pang's sequence 다국어

문제

Prof. Pang is given a fixed sequence $a_1, \ldots, a_n$ and $m$ queries.

Each query is specified by two integers $l$ and $r$ satisfying 1ドル\le l\le r\le n$. For each query, you should answer the number of pairs of integers $(i, j)$ such that $l\le i\le j\le r$ and the number of distinct integers in $a_i, \ldots, a_j$ is odd.

입력

The first line contains a single integer $n$ (1ドル\le n\le 5\times 10^5$).

The next line contains $n$ integers $a_1, \ldots, a_n$ (1ドル\le a_i\le n$ for all 1ドル\le i\le n$) separated by single spaces.

The next line contains a single integer $m$ (1ドル\le m\le 5\times 10^5$).

Each of the next $m$ lines contains two integers $l$ and $r$ (1ドル\le l\le r\le n$) separated by a single space denoting a query.

출력

For each query, output one line containing the answer to that query.

제한

힌트