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