Massimo — Eolymp

Input

La prima riga contiene un intero $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) — il numero di elementi nell'array.

La seconda riga contiene $n$ interi $a_{1}, a_{2}, \dots, a_{n} (- 1 0^{9} \leq a_{i} \leq 1 0^{9})$ a_1, a_2, \ldots, a_n~(-10^9 \le a_i \le 10^9) — gli elementi dell'array.

La terza riga contiene un intero $q (1 \leq q \leq 5 \cdot 1 0^{5})$ q~(1 \le q \le 5 \cdot 10^5) — il numero di query.

Ognuna delle successive $q$ righe contiene due interi positivi $l$ e $r (1 \leq l, r \leq n)$ r~(1 \le l, r \le n), che rappresentano gli estremi di un intervallo. Per ogni query, devi trovare il valore massimo nel sottoarray dalla posizione $l$ alla posizione $r$ , inclusa.

Output

Per ogni query, stampa il valore massimo nell'intervallo corrispondente.

Esempi

Esempio 1

Loading