Prof. Pang's sequence

Time limit3sMemory limit1024 MB

Summary

For each query [l, r], count the subarrays a_i..a_j inside it whose number of distinct values is odd.

Level: Hard10 of 10
Topics: Divide and conquer, Array, Hash map, Dynamic programming
Solved: No attempts yet

Problem

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

Each query gives two integers $l$ and $r$ with $1\le l\le r\le n$ . For each query, count the pairs of integers $(i, j)$ with $l\le i\le j\le r$ such that the number of distinct integers in $a_i, \ldots, a_j$ is odd.

Input

The first line contains one integer $n$ ( $1\le n\le 5\times 10^5$ ).

The second line contains $n$ integers $a_1, \ldots, a_n$ ( $1\le a_i\le n$ ), separated by single spaces.

The next line contains one 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.

Output

For each query, output the answer on its own line.

Examples3

Example 1

Input

Expected output

Example 2

Input

Expected output

Example 3

Input

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

Expected output