El profesor Joi, una autoridad en el estudio de la historia del país IOI, ha recibido un diario que supuestamente escribió un habitante del antiguo país IOI. Para investigar cómo se vivía entonces, ha decidido estudiar los sucesos descritos en el diario.

El diario describe un suceso por día durante $N$ días. Los sucesos se clasifican en varios tipos. El tipo del suceso del día $i$ ($1 \le i \le N$) se representa mediante el entero $X_i$. Se considera que cuanto mayor es $X_i$, mayor es la magnitud del suceso.

El profesor Joi ha decidido analizar el diario de la siguiente manera:

1. Elegir un periodo de varios días consecutivos entre los $N$ días del diario.
2. Definir la importancia del tipo de suceso $t$ como $t$ multiplicado por el número de sucesos de tipo $t$ en ese periodo.
3. Calcular la importancia de todos los tipos de sucesos y obtener su valor máximo.

El profesor Joi te ha encargado escribir un programa para este análisis. El programa debe calcular la importancia máxima cuando se le proporciona el periodo que se desea analizar.

Tarea

Dados los tipos de sucesos de los $N$ días del diario y $Q$ consultas que especifican periodos del diario, escribe un programa que calcule la importancia máxima de los sucesos para cada consulta.

Entrada

Lee los siguientes datos de la entrada estándar.

• La primera línea contiene dos enteros $N,Q$ separados por un espacio. Indican que el diario abarca $N$ días y que se proporcionan $Q$ consultas.
• La siguiente línea contiene $N$ enteros $X_1,\ldots,X_N$ separados por espacios. El valor $X_i$ ($1 \le i \le N$) representa el tipo de suceso del día $i$.
• La $j$-ésima de las siguientes $Q$ líneas ($1 \le j \le Q$) contiene dos enteros $A_j,B_j$ ($1 \le A_j \le B_j \le N$) separados por un espacio. La consulta $j$ corresponde al periodo desde el día $A_j$ hasta el día $B_j$.

Salida

Escribe $Q$ líneas en la salida estándar. La $j$-ésima línea ($1 \le j \le Q$) debe contener un entero que represente la importancia máxima para la consulta $j$.

Restricciones

Todos los datos de entrada satisfacen las siguientes condiciones.

• $1 \le N \le 100\,000$.
• $1 \le Q \le 100\,000$.
• $1 \le X_i \le 1\,000\,000\,000$ ($1 \le i \le N$).

Subtareas

Subtarea 1 [5 puntos]

Se cumplen las siguientes condiciones.

• $N \le 100$.
• $Q \le 100$.

Subtarea 2 [10 puntos]

Se cumplen las siguientes condiciones.

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

Subtarea 3 [25 puntos]

• No existen índices $i,j$ ($1 \le i \le Q$, $1 \le j \le Q$, $i \ne j$) tales que $A_i \le A_j \le B_j \le B_i$.

Subtarea 4 [60 puntos]

No hay restricciones adicionales.

Ejemplos

Entrada 1

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

Salida 1

9
8
8
16
16

Nota

• Este diario abarca $5$ días y los tipos de sucesos que aparecen son $7$, $8$ y $9$.
• Entre los días $1$ y $2$, la importancia del tipo $7$ es $7\times0=0$, la del tipo $8$ es $8\times1=8$ y la del tipo $9$ es $9\times1=9$. Por tanto, el máximo es $9$.
• Entre los días $3$ y $4$, la importancia del tipo $7$ es $7\times1=7$, la del tipo $8$ es $8\times1=8$ y la del tipo $9$ es $9\times0=0$. Por tanto, el máximo es $8$.
• En el día $4$, la importancia del tipo $7$ es $7\times0=0$, la del tipo $8$ es $8\times1=8$ y la del tipo $9$ es $9\times0=0$. Por tanto, el máximo es $8$.
• Entre los días $1$ y $4$, la importancia del tipo $7$ es $7\times1=7$, la del tipo $8$ es $8\times2=16$ y la del tipo $9$ es $9\times1=9$. Por tanto, el máximo es $16$.
• Entre los días $2$ y $4$, la importancia del tipo $7$ es $7\times1=7$, la del tipo $8$ es $8\times2=16$ y la del tipo $9$ es $9\times0=0$. Por tanto, el máximo es $16$.

Entrada 2

8 4
9 9 19 9 9 15 9 19
1 4
4 6
3 5
5 8

Salida 2

27
18
19
19

Nota

Esta entrada satisface las restricciones de la subtarea $3$.

Entrada 3

12 15
15 9 3 15 9 3 3 8 16 9 3 17
2 7
2 5
2 2
1 12
4 12
3 6
11 12
1 7
2 6
3 5
3 10
7 10
1 4
4 8
4 8

Salida 3

18
18
9
30
18
15
17
30
18
15
18
16
30
15
15