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\)