You are given an array consisting of N numbers A1, A2, ... AN
There are Q queries of type [L, R] (1-based indexing)
For each query [L, R], you need to print the count of numbers whose frequency in the given range L to R(inclusive) is equal to the 2nd maximum number in the range [L, R].

Note:
The second maximum number need not be different from the first maximum number. In the following array [5,4,3,2,3,5] the second maximum element is 5 and not 4

Example 1
Let's assume N is 6 and the array is [5,2,2,2,1,3] and the query is [1,6]
The first maximum number in the range is 5, the second maximum number is 3
2 occurs for 3 times. So the output is 2

Sample Input

10
1 2 2 1 3 1 2 2 1 1
4
1 5
1 2
6 8
1 10

Sample Output

2
2
1
0

Explanation
We are given the following array [1,2,2,1,3,1,2,2,1,1]

For the 1st query 1 to 5:
second max = 2
frequency of 1 and 2 is 2 thus the answer to 1st query is 2 (ie 2 numbers have frequency == secondmax)

For 2nd query 1 to 2:
second max = 1
frequency of 1 and 2 is 1 thus the answer is 2

For 3rd query 6 to 8:
second max = 2
frequency of 2 is 2 thus the answer is 1

For 4th query 1 to 10:
second max = 2;
frequency of none of the element in the given range is 2 thus the answer is 0