Given a sequence $A_1, A_2, \ldots, A_N$ of length $N$. All numbers in the sequence are between $1$ and $N$ and are pairwise distinct. Write a program to process the following queries:

• l r: output the number of integer pairs $(x, y)$ such that $l \le x \le y \le r$ and $(max_{i=x}^{y} A_i) - (min_{i=x}^{y} A_i) = y - x$.

Input

The first line contains an integer $N$, the length of the sequence. ($1 \le N \le 120{,}000$)

The second line contains $N$ integers $A_1, A_2, \ldots, A_N$, all distinct. ($1 \le A_i \le N$)

The third line contains an integer $M$, the number of queries. ($1 \le M \le 120{,}000$)

The next $M$ lines each contain a query in the format l r. ($1 \le l \le r \le N$)

Output

For each query, output a line containing one integer — the answer.

Examples

Input 1

5
1 3 2 5 4
5
1 1
1 2
1 3
1 4
1 5

Output 1

1
2
5
6
10