Professor Joy, ein führender Experte für die Geschichte des Landes IOI, hat ein Tagebuch erhalten, das angeblich von einem Bewohner des antiken IOI geschrieben wurde. Um mithilfe dieses Tagebuchs das damalige Leben in IOI zu erforschen, beschließt er, die darin beschriebenen Ereignisse zu untersuchen.

Das Tagebuch beschreibt die Ereignisse von $N$ Tagen, genau eines pro Tag. Die Ereignisse sind in mehrere Arten eingeteilt. Die Art des Ereignisses am $i$-ten Tag ($1 \le i \le N$) wird durch die ganze Zahl $X_i$ angegeben. Je größer $X_i$ ist, desto größer wird das Ausmaß des Ereignisses eingeschätzt.

Professor Joy möchte das Tagebuch folgendermaßen analysieren.

1. Wähle einige aufeinanderfolgende Tage aus den $N$ Tagen des Tagebuchs als Analysezeitraum.
2. Die Bedeutung einer Ereignisart $t$ sei $t \times (\text{Anzahl der Ereignisse der Art } t \text{ in diesem Zeitraum})$.
3. Berechne die Bedeutung für alle Ereignisarten und bestimme den größten Wert.

Professor Joy hat dich beauftragt, ein Programm für diese Analyse zu schreiben. Es soll für einen gegebenen Analysezeitraum den größten Bedeutungswert ermitteln können.

Aufgabe

Gegeben sind die Ereignisarten an den $N$ Tagen des Tagebuchs und $Q$ Anfragen, die jeweils einen Zeitraum im Tagebuch angeben. Schreibe ein Programm, das für jede Anfrage den größten Bedeutungswert einer Ereignisart ermittelt.

Eingabe

Lies die folgenden Daten von der Standardeingabe.

• Die erste Zeile enthält die durch ein Leerzeichen getrennten ganzen Zahlen $N$, $Q$. Das Tagebuch umfasst $N$ Tage, und es werden $Q$ Anfragen gestellt.
• Die nächste Zeile enthält $N$ durch Leerzeichen getrennte ganze Zahlen $X_1,\ldots,X_N$. Dabei bezeichnet $X_i$ ($1 \le i \le N$) die Art des Ereignisses am $i$-ten Tag.
• Die $j$-te Zeile ($1 \le j \le Q$) der folgenden $Q$ Zeilen enthält die durch ein Leerzeichen getrennten ganzen Zahlen $A_j$, $B_j$ ($1 \le A_j \le B_j \le N$). Die $j$-te Anfrage bezieht sich auf den Zeitraum vom $A_j$-ten bis zum $B_j$-ten Tag.

Ausgabe

Gib $Q$ Zeilen auf der Standardausgabe aus. Die $j$-te Zeile ($1 \le j \le Q$) soll eine ganze Zahl enthalten, die den größten Bedeutungswert für die $j$-te Anfrage angibt.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

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

Teilaufgaben

Teilaufgabe 1 [5 Punkte]

Es gelten die folgenden Bedingungen.

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

Teilaufgabe 2 [10 Punkte]

Es gelten die folgenden Bedingungen.

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

Teilaufgabe 3 [25 Punkte]

• Es gibt keine $i,j$ ($1 \le i \le Q$, $1 \le j \le Q$, $i \ne j$) mit $A_i \le A_j \le B_j \le B_i$.

Teilaufgabe 4 [60 Punkte]

Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

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

Ausgabe 1

9
8
8
16
16

Hinweis

• Dieses Tagebuch umfasst 5 Tage. Die darin beschriebenen Ereignisse gehören zu den Arten $7$, $8$ oder $9$.
• Vom 1. bis zum 2. Tag beträgt die Bedeutung der Art $7$ genau $7\times0=0$, die der Art $8$ genau $8\times1=8$ und die der Art $9$ genau $9\times1=9$. Der größte dieser Werte ist also $9$.
• Vom 3. bis zum 4. Tag beträgt die Bedeutung der Art $7$ genau $7\times1=7$, die der Art $8$ genau $8\times1=8$ und die der Art $9$ genau $9\times0=0$. Der größte dieser Werte ist also $8$.
• Am 4. Tag beträgt die Bedeutung der Art $7$ genau $7\times0=0$, die der Art $8$ genau $8\times1=8$ und die der Art $9$ genau $9\times0=0$. Der größte dieser Werte ist also $8$.
• Vom 1. bis zum 4. Tag beträgt die Bedeutung der Art $7$ genau $7\times1=7$, die der Art $8$ genau $8\times2=16$ und die der Art $9$ genau $9\times1=9$. Der größte dieser Werte ist also $16$.
• Vom 2. bis zum 4. Tag beträgt die Bedeutung der Art $7$ genau $7\times1=7$, die der Art $8$ genau $8\times2=16$ und die der Art $9$ genau $9\times0=0$. Der größte dieser Werte ist also $16$.

Eingabe 2

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

Ausgabe 2

27
18
19
19

Hinweis

Diese Eingabe erfüllt die Beschränkungen von Teilaufgabe 3.

Eingabe 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

Ausgabe 3

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