Sequence and Queries 36

A sequence $A_1, A_2, \ldots, A_N$ of length $N$ is given. Every number in the sequence is between 1 and $N$ inclusive, and all numbers are distinct. Write a program that handles the following query.

• l r: Print the number of integer pairs $(x, y)$ with $l \le x \le y \le r$ that satisfy $\left(\max_{i=x}^{y} A_i\right) - \left(\min_{i=x}^{y} A_i\right) = y - x$.

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

The second line contains $A_1, A_2, \ldots, A_N$. All numbers are distinct. ($1 \le A_i \le N$)

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

Each of the following $M$ lines contains one query. ($1 \le l \le r \le N$)

Print the result of each query on its own line.