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\)
In the first query we need to output the sum of all the numbers whose frequency of occurrecne is between 1 and 4 (inclusive). Here all the given numbers have their frequecny between 1 and 4. 3 occurs 3 times, 4 occurs 2 times, 5, 6, 9 occurs 1 time. So total sum would be 3+3+3+4+4+5+6+9 = 37.
