Жизнь программистов

Новый сериал про жизнь программистов содержит $n$ серий, пронумерованных от $1$ до $n$. Телекомпания Сириус ТВ планирует показывать серии по очереди от первой до последней в течение $k$ дней, каждый день показывая блок из одной или нескольких подряд идущих серий. Каждая серия будет показана ровно один раз.

По результатам тестовых просмотров маркетологи компании составили рейтинг серий: $i$-й серии сопоставлено число $a_i$ от $1$ до $n$, самая интересная серия получила рейтинг $1$, а самая скучная --- рейтинг $n$. Рейтинги различных серий различны, поэтому числа $[a_1, a_2, \ldots, a_n]$ образуют перестановку.

Пусть принято решение о том, в какой день какие серии будут показаны. Для каждого дня определим рейтинг этого дня, равный рейтингу самой скучной серии этого дня. Иначе говоря, пусть в $j$-й день показываются серии с $l_j$ по $r_j$, тогда рейтинг этого дня $b_j$ равен максимальному значению среди $[a_{l_j}, a_{l_j+1}, \ldots, a_{r_j}]$.

Чтобы показ сериала был удачным, необходимо вовлечь зрителей в просмотр. Среди всех возможных способов разбить серии на $k$ блоков по дням необходимо выбрать тот, в котором рейтинг первого дня как можно лучше: $b_1$ минимально. Среди этих способов в свою очередь необходимо минимизировать рейтинг второго дня $b_2$, при выбранных значениях $b_1$ и $b_2$ --- минимизировать $b_3$, и так далее. Таким образом, необходимо разбить показ серий на $k$ блоков таким образом, чтобы лексикографически минимизировать последовательность $[b_1, b_2, \ldots, b_k]$.

Вам необходимо ответить на $q$ запросов, каждый из которых задаётся двумя числами: $k$ и $i$. В качестве ответа на запрос необходимо вывести значение $b_i$ --- рейтинг $i$-го дня для оптимального способа показать сериал за $k$ дней.

В первой строке входных данных содержится два целых числа $n$ и $q$ ($1 \le n, q \le 300\,000$) --- количество серий и количество запросов соответственно.

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

Следующие $q$ строк содержат по два целых числа $k$ и $i$ ($1 \le i \le k \le n$) --- параметры очередного запроса.

В $q$ строках выведите ответ на каждый запрос, в том порядке, в котором они даны во входных данных.

Рассмотрим первый тест:

• При $k = 7$ существует единственный способ показа: каждый день показывать по одной серии. Рейтинги серий по дням получаются $[6], [4], [2], [3], [1], [7], [5]$, откуда $b = [6, 4, 2, 3, 1, 7, 5]$, поэтому ответ на запрос $k = 7$ и $i = 4$ равен $b_4 = 3$.
• При $k = 1$ существует единственный способ показа: показать все серии в первый день. Рейтинги серий по дням: $[6, 4, 2, 3, 1, 7, 5]$, откуда $b = [7]$, поэтому ответ на запрос $k = 1$ и $i = 1$ равен $b_1=7$.
• При $k = 4$ оптимально в первый день показать четыре серии, а затем три дня показывать по одной серии. Рейтинги серий по дням: $[6, 4, 2, 3], [1], [7], [5]$, откуда $b = [6, 1, 7, 5]$, поэтому ответ на запрос $k = 4$ и $i = 2$ равен $b_2=1$.
• При $k = 5$ оптимально в первый и последний день показать по две серии, а в остальные дни по одной. Рейтинги серий по дням: $[6, 4], [2], [3], [1], [7, 5]$, откуда $b = [6, 2, 3, 1, 7]$, поэтому ответ на запрос $k = 5$ и $i = 3$ равен $b_3=3$.