Tienes ~n~ monedas con valores enteros positivos. Las monedas están numeradas del ~1~ al ~n~.

Tu tarea es procesar ~q~ consultas del tipo: "Si puedes usar las monedas ~a \dots b~, ¿cuál es la suma mínima que no puedes obtener?".

Entrada

• La primera línea de entrada contiene dos enteros, ~n~ y ~q~: el número de monedas y consultas.
• La segunda línea contiene ~n~ enteros, ~x_1,x_2,\dots,x_n~: el valor de cada moneda.
• Finalmente, hay ~q~ líneas que describen las consultas. Cada línea contiene dos valores, ~a~ y ~b~: puedes usar las monedas ~a \dots b~.

Salida

Imprime la respuesta para cada consulta.

Restricciones

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

Ejemplo de Entrada

5 3
2 9 1 2 7
2 4
4 4
1 5

Ejemplo de Salida

4
1
6

Explicación: Primero se puede usar el intervalo ~[9,1,2]~, luego ~[2]~ y finalmente ~[2,9,1,2,7]~.