CSES - Lämpötila
  • Time limit: 2.00 s
  • Memory limit: 128 MB
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