Se te da una secuencia de enteros $x_1, x_2, \ldots, x_n$. Considera el grafo no dirigido ponderado $G$ con $n$ vértices, numerados del $1$ al $n$, que contiene, para cada par de vértices $u$ y $v$ con $u < v$, la arista $\{u,v\}$ de peso $x_v - x_u$.

Ten en cuenta que $x$ no está necesariamente ordenada, por lo que los pesos de las aristas pueden ser negativos.

Para un par $(\ell,r)$ con $\ell \le r$, sea $G[\ell,r]$ el subgrafo de $G$ inducido por los vértices $\ell, \ell + 1, \ldots, r$; es decir, el grafo sobre esos vértices que conserva exactamente las aristas de $G$ cuyos dos extremos están en ese intervalo. Define $f(\ell,r)$ como el mínimo peso total posible de un árbol de expansión de $G[\ell,r]$. En particular, $f(\ell,\ell) = 0$.

Se te dan $q$ pares $(\ell,r)$. Calcula $f(\ell,r)$ para cada uno de ellos.

Entrada

La primera línea contiene dos enteros $n$ y $q$ ($1 \le n,q \le 2 \cdot 10^5$): la longitud de la secuencia y el número de consultas.

La segunda línea contiene $n$ enteros $x_1, x_2, \ldots, x_n$ ($-10^9 \le x_i \le 10^9$).

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

Salida

Imprime $q$ líneas. La $i$-ésima línea debe contener un único entero: la respuesta a la $i$-ésima consulta.

Ejemplos

Entrada 1

3 4
0 10 0
1 3
1 2
2 3
2 2

Salida 1

-10
10
-10
0

Nota

Para la primera consulta, los pesos de las tres aristas son $10$, $0$ y $-10$. Elegir las aristas de pesos $0$ y $-10$ da un árbol de expansión de peso total $-10$.

La segunda y la tercera consulta contienen dos vértices, por lo que sus respuestas son los pesos de sus únicas aristas: $10$ y $-10$, respectivamente. La última consulta contiene un vértice y, por tanto, su respuesta es $0$.