Se le proporciona un arreglo compuesto por ~n~ enteros. Los elementos del arreglo están indexados como ~1,2,\dots,n~. Puede modificar el arreglo mediante la siguiente operación: seleccione un elemento del arreglo y aumente su valor en uno.

Su tarea consiste en procesar ~q~ consultas de la forma: cuando consideramos un subarreglo desde la posición ~a~ hasta la posición ~b~, ¿cuál es el número mínimo de operaciones tras el cual el subarreglo es creciente?. Un arreglo es creciente si cada elemento es mayor o igual que el elemento anterior.

Entrada

• La primera línea de entrada contiene dos enteros ~n~ y ~q~: el tamaño del arreglo y el número de consultas.
• La siguiente línea contiene ~n~ enteros ~x_1,x_2,\dots,x_n~: el contenido del arreglo.
• Finalmente, hay ~q~ líneas que describen las consultas. Cada línea contiene dos enteros ~a~ y ~b~: la posición inicial y final del subarreglo.

Salida

Para cada consulta, imprima el número mínimo de operaciones.

Restricciones

• ~1 \leq n,q \leq 2\cdot10^5~
• ~1 \leq x_i \leq 10^9~
• ~1 \leq a \leq b \leq n~

Ejemplo de Entrada

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

Ejemplo de Salida

2
0
14