Alice y Bob residen en mundos separados. No importa cuán profundamente anhelen comunicarse, el universo solo responde con un silencio indiferente. Entre sus mundos hay una vasta y silenciosa frontera donde $n$ puertas antiguas se alinean en una fila. Estas puertas han permanecido dormidas durante milenios hasta que un día, quizás conmovidas por los deseos de Alice y Bob, comienzan a despertar.

La $i$-ésima puerta despierta en el día $p_i$. No hay dos puertas que despierten el mismo día; por lo tanto, la secuencia $p_1,p_2,\ldots,p_n$ es una permutación de $\{1,2,\ldots,n\}$.

Una sola puerta despierta es meramente una fractura solitaria en la realidad. Puede llevar un susurro fugaz, pero no puede tender un puente sobre el vacío. Para que un segmento continuo de puertas forme un verdadero camino para Alice y Bob, al menos dos puertas dentro de él deben estar despiertas. Solo entonces el espacio entre los mundos se estabiliza lo suficiente para que sus mensajes crucen de manera segura.

Para cualquier par de índices de puertas $i

Se te dan $q$ consultas. Cada consulta está definida por un intervalo $[L,R]$. Para cada consulta, calcula la suma de los días exactos en los que cada subsegmento continuo válido completamente contenido en $[L,R]$ se vuelve por primera vez capaz de transportar sus mensajes:

$$ \sum_{L \le i < j \le R} \operatorname{sec}(i,j). $$

Si $L=R$, no hay ningún segmento que contenga al menos dos puertas, por lo que la respuesta es $0$.

Entrada

La primera línea contiene dos enteros $n$ y $q$ ($1 \le n,q \le 2\cdot 10^5$).

La segunda línea contiene $n$ enteros $p_1,p_2,\ldots,p_n$ que forman una permutación de $\{1,2,\ldots,n\}$.

Cada una de las siguientes $q$ líneas contiene dos enteros $L$ y $R$ ($1 \le L \le R \le n$), que describen una consulta.

Salida

Imprime $q$ líneas. La $t$-ésima línea debe contener la respuesta a la $t$-ésima consulta.

Ejemplos

Entrada 1

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

Salida 1

18
10
3
0

Nota

Para la primera consulta, los subarreglos de longitud al menos $2$ dentro de $[1,4]$ tienen segundos mínimos $3,3,2,4,2,4$, por lo que la respuesta es $18$.