Input

Line 1: n (1 ≤ n ≤ 10^6).
Line 2: n numbers a1, a2, ..., an (-10^9 ≤ ai ≤ ).
Line 3: q (1 ≤ q ≤ 10^6), the number of d-queries.
In the next q lines, each line contains 2 numbers i, j
representing a d-query (1 ≤ i ≤ j ≤ n).

Output

For each d-query (i, j), print the number of distinct elements in the
subsequence ai, ai+1, ..., aj in a single line.
Example

Input
9
1 2 3 2 4 1 2 3 4
3
1 9
2 4
5 9
2 7

Output
0          //Explanation: all elements have been repeated.
1          //Explanation: only 3 has not repeated.
3          //Explanation: only 4 is repeated, so count only 1, 2 and 3.
3          //Explanation: only 2 is repeated, so count only 3, 4 and 1.