Professor Joy, en ledende forsker på historien til IOI-nasjonen, har mottatt en dagbok som antas å ha blitt skrevet av en gammel innbygger i IOI-nasjonen. For å studere livet i den gamle IOI-nasjonen bestemte professor Joy seg for å undersøke hendelsene som er nedtegnet i dagboken.

Dagboken inneholder opptegnelser over hendelser som fant sted over $N$ dager, med én hendelse registrert for hver dag. Hendelser er klassifisert i flere typer. Typen hendelse på dag $i$ ($1 \le i \le N$) er representert ved et heltall $X_i$. Det antas at jo større verdien av $X_i$ er, desto større var omfanget av hendelsen.

Professor Joy bestemte seg for å analysere dagboken ved hjelp av følgende metode:

1. Velg et sammenhengende antall dager innenfor de $N$ dagene i dagboken som analyseperiode.
2. Viktigheten til en hendelsestype $t$ er definert som $t \times (\text{the number of events of type } t \text{ in that period})$ (altså $t$ multiplisert med antall hendelser av type $t$ i den perioden).
3. Beregn viktigheten for alle hendelsestyper og finn den maksimale verdien.

Du har fått i oppdrag av professor Joy å lage et program for denne analysen. Programmet skal kunne finne den maksimale viktigheten når det får oppgitt en analyseperiode.

Oppgave

Gitt hendelsestypene for de $N$ dagene i dagboken og $Q$ spørringer som representerer perioder i dagboken, skriv et program som finner den maksimale viktigheten av hendelser for hver spørring.

Inndata

Les følgende data fra standard inndata:

• Den første linjen inneholder to heltall $N$ og $Q$ adskilt med et mellomrom, som betyr at dagboken dekker $N$ dager og at det er $Q$ spørringer.
• Neste linje inneholder $N$ heltall $X_1, \dots, X_N$ adskilt med mellomrom, der $X_i$ ($1 \le i \le N$) representerer hendelsestypen på dag $i$.
• Hver av de følgende $Q$ linjene (for $1 \le j \le Q$) inneholder to heltall $A_j$ og $B_j$ ($1 \le A_j \le B_j \le N$) adskilt med et mellomrom, som betyr at den $j$-te spørringen gjelder perioden fra dag $A_j$ til dag $B_j$.

Utdata

Skriv ut $Q$ linjer til standard utdata. Den $j$-te linjen ($1 \le j \le Q$) skal inneholde et heltall som representerer den maksimale viktigheten for den $j$-te spørringen.

Begrensninger

Alle inndata tilfredsstiller følgende betingelser:

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

Deloppgaver

Deloppgave 1 [5 poeng]

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

Deloppgave 2 [10 poeng]

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

Deloppgave 3 [25 poeng]

• Det finnes ingen $i, j$ ($1 \le i \le Q, 1 \le j \le Q, i \neq j$) slik at $A_i \le A_j \le B_j \le B_i$.

Deloppgave 4 [60 poeng]

• Ingen ytterligere begrensninger.

Eksempler

Inndata 1

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

Utdata 1

9
8
8
16
16

Merk 1

• Denne dagboken består av 5 dager, og de registrerte hendelsestypene er 7, 8 eller 9.
• For perioden fra dag 1 til dag 2 er viktigheten til hendelsestype 7 lik $7 \times 0 = 0$, hendelsestype 8 er $8 \times 1 = 8$, og hendelsestype 9 er $9 \times 1 = 9$. Maksimum av disse er 9.
• For perioden fra dag 3 til dag 4 er viktigheten til hendelsestype 7 lik $7 \times 1 = 7$, hendelsestype 8 er $8 \times 1 = 8$, og hendelsestype 9 er $9 \times 0 = 0$. Maksimum av disse er 8.
• For dag 4 er viktigheten til hendelsestype 7 lik $7 \times 0 = 0$, hendelsestype 8 er $8 \times 1 = 8$, og hendelsestype 9 er $9 \times 0 = 0$. Maksimum av disse er 8.
• For perioden fra dag 1 til dag 4 er viktigheten til hendelsestype 7 lik $7 \times 1 = 7$, hendelsestype 8 er $8 \times 2 = 16$, og hendelsestype 9 er $9 \times 1 = 9$. Maksimum av disse er 16.
• For perioden fra dag 2 til dag 4 er viktigheten til hendelsestype 7 lik $7 \times 1 = 7$, hendelsestype 8 er $8 \times 2 = 16$, og hendelsestype 9 er $9 \times 0 = 0$. Maksimum av disse er 16.

Inndata 2

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

Utdata 2

27
18
19
19

Merk 2

Disse inndataene tilfredsstiller begrensningene i Deloppgave 3.

Inndata 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

Utdata 3

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