Dada una secuencia $A_1, A_2, \ldots, A_N$ de longitud $N$. Todos los números en la secuencia están entre $1$ y $N$ y son distintos dos a dos. Escriba un programa que procese las siguientes consultas:

• l r: imprima la cantidad de pares de enteros $(x, y)$ tales que $l \le x \le y \le r$ y $(max_{i=x}^{y} A_i) - (min_{i=x}^{y} A_i) = y - x$.

Entrada

La primera línea contiene un entero $N$, la longitud de la secuencia. ($1 \le N \le 120{,}000$)

La segunda línea contiene $N$ enteros $A_1, A_2, \ldots, A_N$, todos distintos. ($1 \le A_i \le N$)

La tercera línea contiene un entero $M$, la cantidad de consultas. ($1 \le M \le 120{,}000$)

Las siguientes $M$ líneas contienen cada una una consulta en el formato l r. ($1 \le l \le r \le N$)

Salida

Para cada consulta, imprima una línea que contenga un entero — la respuesta.

Ejemplos

Entrada 1

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

Salida 1

1
2
5
6
10