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