Минимум без изменений

Дан массив, который не меняется. Ответьте на большое количество запросов «минимум на отрезке».

В первой строке $n$ ($1 \le n \le 10^5$). Во второй — $n$ чисел $a_i$ ($|a_i| \le 10^9$). В третьей — $k$ ($1 \le k \le 2 \cdot 10^5$). Далее $k$ строк по два числа $l$ и $r$ ($1 \le l \le r \le n$).

Для каждого запроса выведите минимум на отдельной строке.