Shona es un estudiante universitario muy interesado en el estudio de las ondas. Las ondas numéricas se pueden describir usando un arreglo de números enteros no negativos. Por ejemplo, la onda \([0, 5, 8, 9, 2, 3, 2, 1, 10, 5, 3, 2, 1, 7, 0]\).

Una característica especial de estas ondas es que el arreglo que las describe no puede tener dos números repetidos consecutivos, esto significa que, si \(A\) es el arreglo que describe la onda, \(A_i \neq A_{i+1}\) para todo \(0 \leq i < N - 1\), donde \(N\) es el tamaño del arreglo. Además, el primer y el último elemento del arreglo siempre serán 0.

Lo que más interesa de una onda numérica son sus picos: una posición \(i\) (\(0 < i < N - 1\)) es un pico si \(A_{i-1} < A_i\) y \(A_i > A_{i+1}\). En el ejemplo mostrado, los picos se dan en las posiciones \(3, 5, 8, 13\), por lo que la onda tiene 4 picos.

El profesor de Shona le da una onda de longitud \(N\), de la cual Shona debe averiguar, para cada una de \(Q\) consultas, cuántos picos tiene la onda original entre los instantes \(a\) y \(b\) (inclusive). Nota que solo se cuentan los picos de la onda original: no se pueden crear nuevos picos recortando el rango.

La primera línea contiene un entero \(N\) (\(3 \leq N \leq 10^6\)): el tamaño de la onda numérica.

La segunda línea contiene \(N\) enteros \(A_1, A_2, \ldots, A_N\) (\(0 \leq A_i \leq 10^8\)) que describen la onda numérica.

La tercera línea contiene un entero \(Q\) (\(1 \leq Q \leq 10^5\)): la cantidad de consultas.

Luego siguen \(Q\) líneas, cada una con dos enteros \(a\) y \(b\) (\(0 \leq a < b < N\)) que representan el rango de la onda donde se debe realizar el análisis.

Imprime \(Q\) líneas, cada una con un entero que representa la cantidad de picos que tiene la onda original entre los instantes \(a\) y \(b\) de la consulta correspondiente.

Explicación del ejemplo 1

Los picos de la onda original están en las posiciones 3, 5, 8, 13. Para la consulta (2, 13) los cuatro caen en el rango: respuesta 4. Para (0, 2) ninguno cae: 0. Para (0, 5) caen 3 y 5: 2. Para (5, 7) cae solo 5: 1. Para (9, 14) cae solo 13: 1.