La mayor parte de la superficie de un planeta extraterrestre es desértica, por lo que apenas llueve. Todas sus plantas son cactus. Como la lluvia es tan escasa, los cactus han evolucionado una forma de cooperar para almacenar agua.

Una región del planeta es un plano bidimensional que solo tiene direcciones arriba-abajo e izquierda-derecha. En ella hay $N$ cactus juntos en una fila. Cada cactus mide $1$ metro de ancho, y sus alturas pueden diferir. Para embellecer el entorno, solo se dejan los cactus del $S$ al $E$. Después llueve lo suficiente para llenar todas las zonas sobre los cactus que pueden retener agua. El agua se acumula como se muestra abajo. En la figura, considera eliminados los cactus fuera del intervalo indicado por las flechas.

Escribe un programa que, dadas las alturas y un intervalo de cactus restantes, calcule el agua retenida como un área. Se dan como máximo $Q$ intervalos. Cada intervalo se aplica siempre al estado inicial en el que existen todos los cactus.

Debes implementar las siguientes funciones.

• void init( int H[] ): Se llama exactamente una vez al principio. $H$ es un arreglo (vector) de tamaño $N$ que contiene las alturas de los cactus de izquierda a derecha. $N$ es la cantidad de cactus.
• int query( int S, int E ): Devuelve el área de agua retenida tras llover suficientemente cuando solo quedan los cactus del $S$ al $E$ ($1 \le S \le E \le N$). Se llama como máximo $Q$ veces. Todas las llamadas son independientes: eliminar cactus en una llamada no afecta a las demás.

Detalles de implementación

Debes entregar exactamente un archivo llamado cactus.cpp. Este archivo debe implementar las siguientes funciones.

• void init( int H[] )
• long long query( int S, int E )

Las funciones deben comportarse como se ha descrito. Puedes definir otras funciones para uso interno. El código entregado no debe realizar entrada ni salida ni acceder a otros archivos.

Evaluador de ejemplo

El evaluador proporcionado lee la entrada en el siguiente formato.

• Línea 1: $N$, $Q$.
• Siguiente línea: $N$ enteros positivos, las alturas de los cactus de izquierda a derecha.
• Siguientes $Q$ líneas: dos enteros positivos $S,E$, que indican que llueve quedando solo los cactus del $S$ al $E$ ($1 \le S \le E \le N$).

El evaluador proporcionado imprime los valores devueltos por tu función query(), uno por línea.

Restricciones

• $1 \le N \le 500\,000$, $1 \le Q \le 500\,000$; la altura de cada cactus es al menos $1$ y como máximo $10^9$.

Subtareas

Subtareas 1 (13 puntos)

• $1 \le N \le 5\,000$, $1 \le Q \le 5\,000$

Subtareas 2 (12 puntos)

• $1 \le N \le 5\,000$

Subtareas 3 (22 puntos)

• La altura de cada cactus es como máximo $20$.

Subtareas 4 (34 puntos)

• $1 \le N \le 100\,000$, $1 \le Q \le 100\,000$

Subtareas 5 (69 puntos)

• Sin restricciones adicionales a las originales.

Ejemplos

Entrada 1

10 3
1 3 2 5 1 4 6 2 1 3
2 8
2 4
7 9

Nota

A continuación se muestra una ejecución de ejemplo de tu código con la entrada anterior.