시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 2048 MB84120.000%

문제

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

서브태스크

번호배점제한
15

$n \le 20$

28

$k=2$

38

$k=3$

44

Перестановка имеет вид $1$, $n$, $2$, $n-1$, $\ldots$

58

$n \le 200$

67

$n \le 3000$

75

Количество различных значений $k$ во всех запросах не больше $10$

85

$i \le 3$

910

Количество значений $i$, таких что $a_i < a_{i+1}$, не больше $20$

108

Количество значений $i$, таких что $a_i > a_{i+1}$, не больше $20$

1112

Перестановка была выбрана случайно

1210

$n \le 10^5$

1310

예제 입력 1

7 4
6 4 2 3 1 7 5
7 4
1 1
4 2
5 3

예제 출력 1

3
7
1
3

예제 입력 2

3 1
2 3 1
2 2

예제 출력 2

3

노트

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

  • При $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$.

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.