You're given a sequence A of N non-negative integers. Answer Q queries, where each query consists of two integers: a, b. The answer is number of pairs of integers i and j that satisfy these three conditions:

1. 1 <= i <= j <= N
2. a <= j-i+1 <= b
3. all elements of A with indices from range [i, j] are mutually distinct. (indexing starts with 1)

Constraints:
1 <= N <= 8*10^5
1 <= Q <= 2*10^5
0 <= A[k] <= 10^6, for every integer k between 1 and N, inclusive
1 <= a <= b <= N

Input

First line of input contains integer N. Second line contains N integers representing sequence A. Third line is integer Q, number of queries. Next Q lines have 2 integers, a and b.

Output

In the i-th line output the answer for i-th query.

Example

Input:
5
1 2 3 4 5
1
1 1

Output:
5

NOTE: IO is huge