Uolevi on kirjannut muistiin lämpötilan talonsa edustalla n päivän ajalta.

Tehtäväsi on vastata kyselyihin muotoa: mikä oli matalin ja korkein lämpötila tiettynä ajanjaksona?

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

Ohjelmasi tulee tulostaa jokaisesta kyselystä matalin ja korkein lämpötila.

Rajat

• 1 \le n \le 10^5
• -10^9 \le p_k \le 10^9
• 1 \le q \le 10^5
• 1 \le a \le b \le n

Esimerkki

Syöte:

5
2 -1 2 5 1
3
1 3
2 4
3 3

Tuloste:

-1 2
-1 5
2 2