F. Локальные удаления
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для массива $$$b_1, b_2, \ldots, b_m$$$, для индекса $$$i$$$ ($$$1 < i < m$$$) элемент $$$b_i$$$ считается локальным минимумом, если $$$b_i < b_{i-1}$$$ и $$$b_i < b_{i+1}$$$. Элемент $$$b_1$$$ считается локальным минимумом, если $$$b_1 < b_2$$$. Элемент $$$b_m$$$ считается локальным минимумом, если $$$b_m < b_{m-1}$$$.

Для массива $$$b_1, b_2, \ldots, b_m$$$, для индекса $$$i$$$ ($$$1 < i < m$$$) элемент $$$b_i$$$ считается локальным максимумом, если $$$b_i > b_{i-1}$$$ и $$$b_i > b_{i+1}$$$. Элемент $$$b_1$$$ считается локальным максимумом, если $$$b_1 > b_2$$$. Элемент $$$b_m$$$ считается локальным максимумом, если $$$b_m > b_{m-1}$$$.

Пусть $$$x$$$ — массив, в котором все элементы различны. Определим две операции над ним.

  • $$$1$$$ — удалить из $$$x$$$ все элементы, которые не являются локальными минимумами.
  • $$$2$$$ — удалить из $$$x$$$ все элементы, которые не являются локальными максимумами.

Определим $$$f(x)$$$ следующим образом: повторять операции $$$1, 2, 1, 2, \ldots$$$ в таком порядке, пока в массиве не останется только один элемент. В конце вернуть этот элемент.

Например, возьмем массив $$$[1,3,2]$$$. Сначала выполним операцию типа $$$1$$$ и получим $$$[1, 2]$$$. Затем выполним операцию типа $$$2$$$ и получим $$$[2]$$$. Значит, $$$f([1,3,2]) = 2$$$.

Дана перестановка$$$^\dagger$$$ $$$a$$$ длины $$$n$$$ и $$$q$$$ запросов. Каждый запрос состоит из двух целых чисел $$$l$$$ и $$$r$$$ таких, что $$$1 \le l \le r \le n$$$. Для каждого запроса требуется посчитать $$$f([a_l, a_{l+1}, \ldots, a_r])$$$.

$$$^\dagger$$$ Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 10^5$$$) — длину перестановки $$$a$$$ и количество запросов.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы перестановки $$$a$$$.

В $$$i$$$-й из следующих $$$q$$$ строк содержатся два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — описание $$$i$$$-го запроса.

Выходные данные

Для каждого запроса выведите одно целое число — ответ на этот запрос.

Примеры
Входные данные
7 5
1 4 3 6 2 7 5
1 1
1 2
2 3
1 4
1 7
Выходные данные
1
1
3
3
3
Входные данные
10 1
1 2 3 4 5 6 7 8 9 10
1 10
Выходные данные
1
Примечание

В первом запросе первого примера единственным числом в подотрезке массива является $$$1$$$, поэтому оно и является ответом.

Во втором запросе первого примера наш подотрезок изначально имеет вид $$$[1, 4]$$$. После выполнения операции типа $$$1$$$ мы получаем $$$[1]$$$.

В третьем запросе первого примера наш подотрезок изначально имеет вид $$$[4, 3]$$$. После выполнения операции типа $$$1$$$ мы получаем $$$[3]$$$.

В четвертом запросе первого примера наш подотрезок изначально имеет вид $$$[1, 4, 3, 6]$$$. После выполнения операции типа $$$1$$$ мы получаем $$$[1, 3]$$$. Затем выполняем операцию типа $$$2$$$ и получаем $$$[3]$$$.

В пятом запросе первого примера наш подотрезок изначально имеет вид $$$[1, 4, 3, 6, 2, 7, 5]$$$. После выполнения операции типа $$$1$$$ мы получаем $$$[1,3,2,5]$$$. После выполнения операции типа $$$2$$$ получаем $$$[3,5]$$$. Затем выполняем операцию типа $$$1$$$ и получаем $$$[3]$$$.

В первом и единственном запросе второго примера наш подотрезок изначально имеет вид $$$[1,2,3,4,5,6,7,8,9,10]$$$. Здесь $$$1$$$ — единственный локальный минимум, поэтому после выполнения операции типа $$$1$$$ остается только он.