Se dă un șir cu $n$ numere întregi și $q$ query-uri de forma $x, y$.

Să se răspundă, în ordine, la fiecare query care are semnificația: „Se șterg din șir elementele cu pozițiile cuprinse între $x$ și $y$. Care este minimul dintre valorile elementelor rămase din șir?”. ATENȚIE! Operația de ștergere a numerelor cu pozițiile cuprinse între $x$ și $y$ presupune înlocuirea elementelor cu poziții strict mai mari decât $y$, în ordine, pe pozițiile mai mari decât $x$. Numărul de elemente se va reduce cu $y-x+1$ după fiecare query.

Date de intrare

Pe prima linie se află numărul natural $n$.

Începând cu a doua linie, se află $n$ numere întregi dispuse pe una sau mai multe linii, separate prin spații, reprezentând elementele șirului.

Pe următoarea linie se află numărul natural $q$.

Pe următoarele $q$ linii se află câte două numere naturale $x$ și $y$, descrise mai sus.

Date de ieșire

Se vor afișa pe $q$ linii răspunsurile la cele $q$ query-uri, în ordine.

Restricții și precizări

• $1 \leq n \leq 100 \ 000$;
• $1 \leq q \lt n$;
• Fiecare valoare din șir este număr întreg și aparține intervalului $[-10^9$, $10^9]$;
• Este garantat că după fiecare operație șirul nu va rămâne niciodată vid;
• Este garantat că, la fiecare query, $x$ și $y$ se referă la poziții existente din șirul de la momentul respectiv;
• ATENȚIE! Operația de ștergere a numerelor cu pozițiile cuprinse între $x$ și $y$ presupune înlocuirea elementelor cu poziții strict mai mari decât $y$, în ordine, pe pozițiile mai mari decât $x$. Numărul de elemente se va reduce cu $y-x+1$.

Subtask 1 (30 puncte)

• $2 \leq n \leq 1 \ 000$

Subtask 2 (70 puncte)

• $1 \ 001 \leq n \leq 100 \ 000$

Exemplu

stdin

5
1 5 -4 0 3
3
3 3
3 4
1 1

stdout

0
1
5

Explicație

După ștergerea elementului de pe poziția a treia, șirul rezultat este $[1, 5, 0, 3]$, deci minimul este $0$.

După ștergerea elementelor de pe pozițiile $3$ și $4$ din noul șir, șirul rezultat este $[1, 5]$, deci minimul este $1$.

După ștergerea elementului de pe prima poziție, șirul rezultat este $[5]$, deci minimul este $5$.