- Time limit: 2.00 s
- Memory limit: 512 MB
Uolevi on jälleen kerran kirjannut muistiin lämpötilan talonsa edustalla n päivän ajalta. Tällä kertaa tehtävänäsi on vastata kyselyihin muotoa: kuinka paljon lämpötila oli suurimmillaan kasvanut tiettynä ajanjaksona. Toisin sanoen sinun täytyy löytää ajanjaksolta kaksi päivää i ja j niin että i \le j ja p_j - p_i on mahdollisimman suuri.
Syöte
Syötteen ensimmäisellä rivillä on kokonaisluku n: päivien määrä.
Seuraavalla rivillä on n kokonaislukua p_1,p_2,\ldots,p_n: lämpötila kunakin päivänä.
Sitten syötteessä on kokonaisluku q: kyselyiden määrä.
Lopuksi syötteessä on q riviä, joista jokaisella on kaksi kokonaislukua a ja b: tutkittavan välin aloituspäivä ja lopetuspäivä.
Tuloste
Tulosta jokaiselle välille kuinka paljon lämpötila oli suurimmillaan kasvanut kyseisenä ajanjaksona.
Rajat
- 1 \le n \le 2 \cdot 10^5
- -10^9 \le p_i \le 10^9
- 1 \le q \le 2 \cdot 10^5
- 1 \le a \le b \le n
Esimerkki
Syöte:
8 2 1 6 4 3 4 9 2 5 1 4 3 6 5 8 2 3 3 5
Tuloste:
5 1 6 5 0