Napoleon má v rade nastúpených $N$ plukov, očíslovaných zľava doprava (zľava z Napoleonovho pohľadu!) od $1$ po $N$. Pluk $i$ má silu $p_i$. Napoleon čaká, že keď nepriateľ zaútočí, tak zaútočí na súvislý úsek plukov. Chcel by teraz premyslieť rôzne možnosti útoku. Pri tom bude skúmať rôzne úseky svojich plukov. Zakaždým by potreboval rýchlo vedieť, aký najslabší a aký najsilnejší pluk je v danom úseku.
Úlohu odporúčame vyriešiť rýchlo a správne — Napoleonova obľúbená fráza je: "Pane, ste odo mňa o hlavu vyšší, tento rozdiel sa ale dá rýchlo napraviť..."
V prvom riadku vstupu je celé číslo $T$ udávajúce počet sád testovacích údajov, najviac $100$. Nasleduje $T$ sád údajov.
Každá sada údajov začína riadkom obsahujúcim celé číslo $N$ $(1 \leq N \leq 10^6)$. V druhom riadku je $N$ medzerami oddelených celých čísel $p_1, \dots, p_N$ $(-10^9 \leq p_i \leq 10^9)$. V treťom riadku je jedno celé číslo $M$ $(1 \leq M \leq 10^5)$, udávajúce počet Napoleonových otázok. Nasleduje $M$ riadkov. Každý z nich obsahuje dve celé čísla $A$ a $B$ $(1 \leq A \leq B \leq N)$ — najmenšie a najväčšie číslo pluku v úseku, ktorý Napoleona práve zaujíma.
Pre každú sadu testovacích údajov vypíšte jeden riadok a v ňom dve medzerou oddelené celé čísla — minimum a maximum spomedzi síl plukov v zadanom úseku.
2
6
1 2 3 4 5 6
2
1 4
5 5
6
6 1 4 2 100 0
3
5 6
1 3
2 4
1 4
5 5
0 100
1 6
1 4