Il professor Joy, uno dei massimi ricercatori nella storia della nazione IOI, ha ricevuto un diario che si ritiene sia stato scritto da un antico abitante della nazione IOI. Per studiare la vita nell'antica nazione IOI, il professor Joy ha deciso di indagare sugli eventi registrati nel diario.

Il diario contiene le registrazioni degli eventi verificatisi nell'arco di $N$ giorni, con un evento registrato per ciascun giorno. Gli eventi sono classificati in diversi tipi. Il tipo di evento nel giorno $i$ ($1 \le i \le N$) è rappresentato da un intero $X_i$. Si ritiene che maggiore è il valore di $X_i$, maggiore sia la portata dell'evento.

Il professor Joy ha deciso di analizzare il diario utilizzando il seguente metodo:

1. Scegliere un numero consecutivo di giorni all'interno degli $N$ giorni del diario come periodo di analisi.
2. L'importanza di un tipo di evento $t$ è definita come $t \times (\text{the number of events of type } t \text{ in that period})$ (ossia $t$ moltiplicato per il numero di eventi di tipo $t$ in quel periodo).
3. Calcolare l'importanza per tutti i tipi di evento e trovare il valore massimo.

Il professor Joy vi ha incaricato di creare un programma per questa analisi. Il programma deve essere in grado di trovare la massima importanza quando gli viene fornito un periodo di analisi.

Compito

Dati i tipi di evento per gli $N$ giorni del diario e $Q$ query che rappresentano periodi nel diario, scrivere un programma che trovi la massima importanza degli eventi per ciascuna query.

Input

Leggere i seguenti dati dallo standard input:

• La prima riga contiene due interi $N$ e $Q$ separati da uno spazio, che indicano che il diario copre $N$ giorni e ci sono $Q$ query.
• La riga successiva contiene $N$ interi $X_1, \dots, X_N$ separati da spazi, dove $X_i$ ($1 \le i \le N$) rappresenta il tipo di evento nel giorno $i$.
• Ciascuna delle seguenti $Q$ righe (per $1 \le j \le Q$) contiene due interi $A_j$ e $B_j$ ($1 \le A_j \le B_j \le N$) separati da uno spazio, che indicano che la $j$-esima query riguarda il periodo dal giorno $A_j$ al giorno $B_j$.

Output

Stampare $Q$ righe sullo standard output. La $j$-esima riga ($1 \le j \le Q$) deve contenere un intero che rappresenta la massima importanza per la $j$-esima query.

Vincoli

Tutti i dati di input soddisfano le seguenti condizioni:

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

Subtask

Subtask 1 [5 punti]

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

Subtask 2 [10 punti]

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

Subtask 3 [25 punti]

• Non esistono $i, j$ ($1 \le i \le Q, 1 \le j \le Q, i \neq j$) tali che $A_i \le A_j \le B_j \le B_i$.

Subtask 4 [60 punti]

• Nessun vincolo aggiuntivo.

Esempi

Input 1

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

Output 1

9
8
8
16
16

Nota 1

• Questo diario è composto da 5 giorni e i tipi di evento registrati sono 7, 8 o 9.
• Per il periodo dal giorno 1 al giorno 2, l'importanza del tipo di evento 7 è $7 \times 0 = 0$, del tipo di evento 8 è $8 \times 1 = 8$ e del tipo di evento 9 è $9 \times 1 = 9$. Il massimo tra questi è 9.
• Per il periodo dal giorno 3 al giorno 4, l'importanza del tipo di evento 7 è $7 \times 1 = 7$, del tipo di evento 8 è $8 \times 1 = 8$ e del tipo di evento 9 è $9 \times 0 = 0$. Il massimo tra questi è 8.
• Per il giorno 4, l'importanza del tipo di evento 7 è $7 \times 0 = 0$, del tipo di evento 8 è $8 \times 1 = 8$ e del tipo di evento 9 è $9 \times 0 = 0$. Il massimo tra questi è 8.
• Per il periodo dal giorno 1 al giorno 4, l'importanza del tipo di evento 7 è $7 \times 1 = 7$, del tipo di evento 8 è $8 \times 2 = 16$ e del tipo di evento 9 è $9 \times 1 = 9$. Il massimo tra questi è 16.
• Per il periodo dal giorno 2 al giorno 4, l'importanza del tipo di evento 7 è $7 \times 1 = 7$, del tipo di evento 8 è $8 \times 2 = 16$ e del tipo di evento 9 è $9 \times 0 = 0$. Il massimo tra questi è 16.

Input 2

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

Output 2

27
18
19
19

Nota 2

Questo input soddisfa i vincoli del Subtask 3.

Input 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

Output 3

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