- Time limit: 1.00 s
- Memory limit: 512 MB
Sinulla on tiedossa Pellecoin-virtuaalivaluutan arvo n päivän ajalta.
Tehtäväsi on vastata q kyselyyn muotoa: mikä oli suurin arvo päivien a ja b välillä?
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja q: päivien ja kyselyiden määrä. Päivät on numeroitu 1,2,\dots,n.
Seuraavalla rivillä on n kokonaislukua x_1,x_2,\dots,x_n: valuutan arvo kunakin päivänä.
Lopuksi on q riviä, jotka kuvaavat kyselyt. Jokaisella rivillä on kaksi kokonaislukua a ja b: alku- ja loppupäivä.
Tuloste
Tulosta jokaista kyselyä kohden yksi kokonaisluku: suurin valuutan arvo.
Rajat
- 1 \le n, q \le 2 \cdot 10^5
- 1 \le x_i \le 10^9
- 1 \le a \le b \le n
Esimerkki
Syöte:
5 3 2 3 1 3 4 1 2 2 4 3 3
Tuloste:
3 3 1