Professori Joy, IOI-valtion historian johtava tutkija, on saanut haltuunsa päiväkirjan, jonka uskotaan olevan muinaisen IOI-valtion asukkaan kirjoittama. Tutkiakseen elämää muinaisessa IOI-valtiossa professori Joy päätti selvittää päiväkirjaan kirjattuja tapahtumia.

Päiväkirja sisältää merkinnät $N$ päivän aikana sattuneista tapahtumista, yhden tapahtuman kultakin päivältä. Tapahtumat on luokiteltu useisiin tyyppeihin. Päivän $i$ ($1 \le i \le N$) tapahtumatyyppiä kuvaa kokonaisluku $X_i$. Uskotaan, että mitä suurempi luvun $X_i$ arvo on, sitä suurempi on tapahtuman mittakaava.

Professori Joy päätti analysoida päiväkirjaa seuraavalla menetelmällä:

1. Valitaan päiväkirjan $N$ päivän joukosta peräkkäisten päivien jakso analyysijaksoksi.
2. Tapahtumatyypin $t$ merkittävyys määritellään kaavalla $t \times (\text{the number of events of type } t \text{ in that period})$ (eli $t$ kerrottuna tyypin $t$ tapahtumien lukumäärällä kyseisellä jaksolla).
3. Lasketaan merkittävyys kaikille tapahtumatyypeille ja etsitään suurin arvo.

Professori Joy on antanut sinulle tehtäväksi laatia ohjelman tätä analyysia varten. Ohjelman tulee pystyä etsimään suurin merkittävyys, kun sille annetaan analyysijakso.

Tehtävä

Kun annetaan tapahtumatyypit päiväkirjan $N$ päivälle sekä $Q$ päiväkirjan jaksoja kuvaavaa kyselyä, kirjoita ohjelma, joka etsii tapahtumien suurimman merkittävyyden kullekin kyselylle.

Syöte

Lue seuraavat tiedot vakiosyötteestä:

• Ensimmäinen rivi sisältää kaksi välilyönnillä erotettua kokonaislukua $N$ ja $Q$, jotka ilmaisevat, että päiväkirja kattaa $N$ päivää ja kyselyjä on $Q$.
• Seuraava rivi sisältää $N$ välilyönnein erotettua kokonaislukua $X_1, \dots, X_N$, missä $X_i$ ($1 \le i \le N$) ilmaisee tapahtumatyypin päivänä $i$.
• Kukin seuraavista $Q$ rivistä (kun $1 \le j \le Q$) sisältää kaksi välilyönnillä erotettua kokonaislukua $A_j$ ja $B_j$ ($1 \le A_j \le B_j \le N$), jotka ilmaisevat, että $j$-s kysely koskee jaksoa päivästä $A_j$ päivään $B_j$.

Tuloste

Tulosta $Q$ riviä vakiotulosteeseen. $j$-nnen rivin ($1 \le j \le Q$) tulee sisältää kokonaisluku, joka ilmaisee suurimman merkittävyyden $j$-nnelle kyselylle.

Rajoitukset

Kaikki syötetiedot täyttävät seuraavat ehdot:

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

Osatehtävät

Osatehtävä 1 [5 pistettä]

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

Osatehtävä 2 [10 pistettä]

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

Osatehtävä 3 [25 pistettä]

• Ei ole olemassa sellaisia $i, j$ ($1 \le i \le Q, 1 \le j \le Q, i \neq j$), joille $A_i \le A_j \le B_j \le B_i$.

Osatehtävä 4 [60 pistettä]

• Ei lisärajoituksia.

Esimerkit

Syöte 1

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

Tuloste 1

9
8
8
16
16

Huomautus 1

• Tämä päiväkirja koostuu 5 päivästä, ja kirjatut tapahtumatyypit ovat 7, 8 tai 9.
• Jaksolla päivästä 1 päivään 2 tapahtumatyypin 7 merkittävyys on $7 \times 0 = 0$, tapahtumatyypin 8 on $8 \times 1 = 8$ ja tapahtumatyypin 9 on $9 \times 1 = 9$. Näistä suurin on 9.
• Jaksolla päivästä 3 päivään 4 tapahtumatyypin 7 merkittävyys on $7 \times 1 = 7$, tapahtumatyypin 8 on $8 \times 1 = 8$ ja tapahtumatyypin 9 on $9 \times 0 = 0$. Näistä suurin on 8.
• Päivälle 4 tapahtumatyypin 7 merkittävyys on $7 \times 0 = 0$, tapahtumatyypin 8 on $8 \times 1 = 8$ ja tapahtumatyypin 9 on $9 \times 0 = 0$. Näistä suurin on 8.
• Jaksolla päivästä 1 päivään 4 tapahtumatyypin 7 merkittävyys on $7 \times 1 = 7$, tapahtumatyypin 8 on $8 \times 2 = 16$ ja tapahtumatyypin 9 on $9 \times 1 = 9$. Näistä suurin on 16.
• Jaksolla päivästä 2 päivään 4 tapahtumatyypin 7 merkittävyys on $7 \times 1 = 7$, tapahtumatyypin 8 on $8 \times 2 = 16$ ja tapahtumatyypin 9 on $9 \times 0 = 0$. Näistä suurin on 16.

Syöte 2

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

Tuloste 2

27
18
19
19

Huomautus 2

Tämä syöte täyttää Osatehtävän 3 rajoitukset.

Syöte 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

Tuloste 3

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