Задача: Стражите на планината
Ограничение по време: 1 секунда
Ограничение по памет: 256 MB

В далечно царство, на върха на голяма планина, стоят стражи, които наблюдават пътя надолу към селата. Всеки страж има сила, която показва колко добре може да пази селото от набези.

Кралството иска да проверява безопасността на пътя между два стража. Той пита:
"Кой е най-слабият страж между страж A и страж B? Ако той бъде нападнат, селото ще е в опасност."

Ти, като млад стратег, трябва да помагаш на краля, като отговаряш на тези въпроси бързо.

Вход:
Първият ред съдържа числата n и q — броят на стражите и броят въпроси.
Вторият ред съдържа n числа s_1, s_2, ..., s_n — силата на всеки страж по реда, по който стоят на планината.
Следват q реда, всеки с две числа l и r — диапазона от стражи, за които кралят пита.

Изход:
За всеки въпрос отпечатай силата на най-слабия страж между l и r.

Ограничения:
1 ≤ n, q ≤ 10^5
1 ≤ s_i ≤ 10^9
1 ≤ l ≤ r ≤ n

Подзадачи:
(30 точки)
1 ≤ n, q ≤ 1000

(30 точки)
1 ≤ n, q ≤ 10^5
Всички s_i ≤ 10^5

(40 точки)
1 ≤ n, q ≤ 10^5
1 ≤ s_i ≤ 10^9

Пример:
Вход:
5 3
4 2 5 1 3
1 3
2 4
3 5

Изход:
2
1
1