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

Новый сериал про жизнь программистов содержит $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$.