Problem Statement

$N$ people numbered $1,2,\dots,N$ are standing in a row. Person $i$ wears Color $A_i$.

Answer $Q$ queries of the format below.

• You are given integers $l$ and $r$. Considering only Person $l,l+1,\dots,r$, how many pairs of people wearing the same color can be formed at most?

Constraints

• All values in input are integers.
• $1 \le N \le 10^5$
• $1 \le Q \le 10^6$
• $1 \le A_i \le N$
• $1 \le l \le r \le N$ in each query.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N
Q
\mathrm{Query}_1
\mathrm{Query}_2
\vdots
\mathrm{Query}_Q

Here, $\mathrm{Query}_i$ represents the $i$-th query.

Each query is in the following format:

l r

Output

Print $Q$ lines. The $i$-th line should contain the answer for the $i$-th query as an integer. The use of fast input and output methods is recommended because of potentially large input and output.