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⁵
1 ≤ Q ≤ 2×10⁵
0 ≤ A[k] ≤ 10⁶, 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