There are $N$ numbers $A1, A2, ..., An$, and you are given $Q$ queries. In each query, you are given two integers $l$ and $r$.

You are required to print the sum of all the numbers whose frequency of occurrence is between $l$ and $r$ (including $l$ and $r$). Print a single integer for each query in a new line.

Input format

• The first line contains $N$ denoting the size of the array.
• The second line contains $N$ integers denoting the elements of the array.
• The third line contains $Q$ denoting the number of queries.
• Next $Q$ lines contain $l$ and $r$. 

Output format

For each query, print the sum of all elements of the array whose frequency of occurrence is between $l$ and $r$ (inclusive) in a new line.

Constraints

$1 \leq N \leq 1000000$

$1 \leq Ai \leq 1000000$

$1 \leq Q \leq 1000000$

$1 \leq l \leq r \leq N$