Chomu loves solving problems related to queries. But for now he is too busy in eating. So, he wants you to solve this problem to maintain his reputation in the programming world.
You are given an array of n numbers a1, a2, ... an. You are also given q queries for each query you have to output the number of CHOMU pairs in the given range.
A pair (i, j) is called CHOMU, if i < j and (a[i] != a[j]). Here, (i, j) represents the indices in the given array.
Input Format
The first line of input contains a single integer N denoting the number of elements in the array. The second line contains the elements in the array itself. The third line contains the number of queries Q.
Next Q lines containes a query.
A query contains two integers [l, r] denoting the range in the given array.
l and r are 0-indexed.
Constraints
1 <= N <= 300000
-100000 <= a[i] <= 100000
1 <= Q <= 300000
0 <= l <= r < N
Output Format
For each query output a number denoting the number of CHOMU pairs.
For [0, 4] all pairs except (1, 1) are counted.
For [0, 2] all pairs except (1, 1) are counted.
For [2, 4] pairs include (1, 3), (3, 5), (1, 5), so answer is 3.
For [1, 3] pairs include (2, 1), (2, 3), (1, 3), so answer is 3.
