Для массива \(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\)).
Примечание
В первом запросе первого примера единственным числом в подотрезке массива является \(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\) остается только он.