Задача №115403. Жизнь программистов
Новый сериал про жизнь программистов содержит \(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\).
| Доп. ограничения | ||||
| Подзадача | Баллы | \(n\) | дополнительно | Необх. подзадачи |
| 1 | 5 | \(n \le 20\) | – | У |
| 2 | 8 | – | \(k=2\) | – |
| 3 | 8 | – | \(k=3\) | – |
| 4 | 4 | – | Перестановка имеет вид \(1\), \(n\), \(2\), \(n-1\), ... | – |
| 5 | 8 | \(n \le 200\) | – | У, 1 |
| 6 | 7 | \(n \le 3000\) | – | У, 1, 5 |
| 7 | 5 | – | Количество различных значений \(k\) во всех запросах не больше \(10\) | У, 2, 3 |
| 8 | 5 | – | \(i \le 3\) | – |
| 9 | 10 | – | Количество значений \(i\), таких что \(a_i \lt a_{i+1}\), не больше \(20\) | У, 1 |
| 10 | 8 | – | Количество значений \(i\), таких что \(a_i \gt a_{i+1}\), не больше \(20\) | У, 1 |
| 11 | 12 | – | Перестановка была выбрана случайно | – |
| 12 | 10 | \(n \le 10^5\) | – | У, 1, 5, 6 |
| 13 | 10 | – | – | У, 1–12 |
7 4 6 4 2 3 1 7 5 7 4 1 1 4 2 5 3
3 7 1 3
3 1 2 3 1 2 2
3