O professor Joy, uma autoridade no estudo da história do país IOI, recebeu um diário que supostamente foi escrito por um habitante do antigo país IOI. Para estudar a vida naquela época a partir do diário, o professor decidiu investigar os acontecimentos nele descritos.

O diário registra um acontecimento por dia ao longo de $N$ dias. Os acontecimentos são classificados em vários tipos. O tipo do acontecimento do dia $i$ ($1 \le i \le N$) é representado pelo inteiro $X_i$. Considera-se que, quanto maior o valor de $X_i$, maior a escala do acontecimento.

O professor Joy decidiu analisar o diário da seguinte maneira:

1. Escolher alguns dias consecutivos entre os $N$ dias do diário como período de análise.
2. Definir a importância do tipo de acontecimento $t$ como $t$ multiplicado pelo número de acontecimentos do tipo $t$ nesse período.
3. Calcular a importância de todos os tipos de acontecimentos e obter o maior desses valores.

O professor Joy encarregou você de criar um programa para a análise. Dado um período de análise, esse programa deverá calcular a importância máxima.

Tarefa

Dados os tipos dos acontecimentos dos $N$ dias do diário e $Q$ consultas que representam períodos do diário, escreva um programa que calcule a importância máxima dos acontecimentos para cada consulta.

Entrada

Leia os seguintes dados da entrada padrão.

• A primeira linha contém os inteiros $N,Q$, separados por um espaço. Isso significa que o diário abrange $N$ dias e que serão dadas $Q$ consultas.
• A linha seguinte contém $N$ inteiros $X_1,\ldots,X_N$, separados por espaços, em que $X_i$ ($1 \le i \le N$) representa o tipo do acontecimento do dia $i$.
• A $j$-ésima linha ($1 \le j \le Q$) das próximas $Q$ linhas contém os inteiros $A_j,B_j$ ($1 \le A_j \le B_j \le N$), separados por um espaço. Isso indica que a $j$-ésima consulta corresponde ao período do dia $A_j$ ao dia $B_j$.

Saída

Escreva $Q$ linhas na saída padrão. Na $j$-ésima linha ($1 \le j \le Q$), escreva um inteiro que represente a importância máxima para a $j$-ésima consulta.

Restrições

Todos os dados de entrada satisfazem as seguintes condições.

• $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$).

Subtarefas

Subtarefa 1 [5 pontos]

As seguintes condições são satisfeitas.

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

Subtarefa 2 [10 pontos]

As seguintes condições são satisfeitas.

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

Subtarefa 3 [25 pontos]

• Não existem $i,j$ ($1 \le i \le Q$, $1 \le j \le Q$, $i \ne j$) tais que $A_i \le A_j \le B_j \le B_i$.

Subtarefa 4 [60 pontos]

Não há restrições adicionais.

Exemplos

Entrada 1

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

Saída 1

9
8
8
16
16

Explicação

• Este diário abrange 5 dias, e os tipos dos acontecimentos nele registrados são $7$, $8$ ou $9$.
• Do dia $1$ ao dia $2$, a importância do tipo $7$ é $7 \times 0=0$, a do tipo $8$ é $8 \times 1=8$ e a do tipo $9$ é $9 \times 1=9$. Portanto, o máximo desses valores é $9$.
• Do dia $3$ ao dia $4$, a importância do tipo $7$ é $7 \times 1=7$, a do tipo $8$ é $8 \times 1=8$ e a do tipo $9$ é $9 \times 0=0$. Portanto, o máximo desses valores é $8$.
• No dia $4$, a importância do tipo $7$ é $7 \times 0=0$, a do tipo $8$ é $8 \times 1=8$ e a do tipo $9$ é $9 \times 0=0$. Portanto, o máximo desses valores é $8$.
• Do dia $1$ ao dia $4$, a importância do tipo $7$ é $7 \times 1=7$, a do tipo $8$ é $8 \times 2=16$ e a do tipo $9$ é $9 \times 1=9$. Portanto, o máximo desses valores é $16$.
• Do dia $2$ ao dia $4$, a importância do tipo $7$ é $7 \times 1=7$, a do tipo $8$ é $8 \times 2=16$ e a do tipo $9$ é $9 \times 0=0$. Portanto, o máximo desses valores é $16$.

Entrada 2

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

Saída 2

27
18
19
19

Explicação

Esta entrada satisfaz as restrições da subtarefa 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

Saída 3

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