P12508 「ROI 2025 Day2」程序员的日常

**译自 [ROI 2025](https://neerc.ifmo.ru/school/archive/2024-2025.html) Day2 T4.** ***[Жизнь программистов](https://neerc.ifmo.ru/school/archive/2024-2025/ru-olymp-roi-2025-day2.pdf)*** 一部关于程序员生活的全新电视剧即将在天狼星电视台播出！这部剧共有 $n$ 集，编号从 $1$ 到 $n$。电视台计划在 $k$ 天内按顺序从第一集到最后一集播放，每天播出一个或多个连续剧集的放送块。每集都恰好播放一次。 经过试播反馈，市场团队为每集评定了吸引力指数：第 $i$ 集的指数为 $a_i$，范围从 $1$ 到 $n$，其中 $1$ 表示最吸引人的剧集，$n$ 表示最无聊的剧集。每集的指数互不相同，因此 $[a_1, a_2, \ldots, a_n]$ 构成一个从 $1$ 到 $n$ 的排列。 假设你已经决定好每天播放哪些剧集。每天的吸引力指数定义为当天播放的最无聊剧集的指数。换句话说，如果第 $j$ 天播放从第 $l_j$ 集到第 $r_j$ 集，那么当天的指数 $b_j$ 是 $[a_{l_j}, a_{l_j+1}, \ldots, a_{r_j}]$ 中的最大值。 为了让这部剧大获成功，吸引观众持续追剧，你需要在所有可能的 $k$ 天放送方案中，找到一个让每天的吸引力指数序列 $[b_1, b_2, \ldots, b_k]$ 字典序最小的方案。具体来说，先尽量让第一天的 $b_1$ 最小；在 $b_1$ 最优的情况下，尽量让第二天的 $b_2$ 最小；依此类推。 你需要回答 $q$ 个询问，每个询问由两个数字 $k$ 和 $i$ 组成。你要输出在 $k$ 天放送的最佳方案中，第 $i$ 天的吸引力指数 $b_i$。

第一行包含两个整数 $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, a_2, \ldots, a_n]$ 是从 $1$ 到 $n$ 的一个排列。 接下来的 $q$ 行，每行包含两个整数 $k$ 和 $i$ $(1 \le i \le k \le n)$，表示一个询问的放送天数和需要查询的天数。

输出 $q$ 行，按输入顺序回答每个询问，输出最佳方案中第 $i$ 天的吸引力指数 $b_i$。

### 样例解释 1 - 当 $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$ 时，最优方案是第一天播出 $4$ 集，之后三天每天播出 $1$ 集。每日剧集的吸引力指数为 $[6, 4, 2, 3], [1], [7], [5]$，因此 $b = [6, 1, 7, 5]$。对于询问 $k = 4$ 和 $i = 2$，答案为 $b_2 = 1$。 - 当 $k = 5$ 时，最优方案是第一天和最后一天各播出 $2$ 集，其余三天每天播出 $1$ 集。每日剧集的吸引力指数为 $[6, 4], [2], [3], [1], [7, 5]$，因此 $b = [6, 2, 3, 1, 7]$。对于询问 $k = 5$ 和 $i = 3$，答案为 $b_3 = 3$。 --- 详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。 | 子任务 | 分值 | 附加限制 | | :-: | :-: | :-: | |$0$|$0$|样例|| | $1$ | $5$ | $n \le 20$ | $0$ | | $2$ | $8$ | $k = 2$ | | | $3$ | $8$ | $k = 3$ | | | $4$ | $4$ | 排列形如 $1, n, 2, n-1, \ldots$ | | | $5$ | $8$ | $n \le 200$ | $0,1$ | | $6$ | $7$ | $n \le 3000$ | $0,1,5$ | | $7$ | $5$ | 所有询问的 $k$ 值总数不超过 $10$ | $0,2,3$ | | $8$ | $5$ | $i \le 3$ | | | $9$ | $10$ | 满足 $a_i < a_{i+1}$ 的 $i$ 数量不超过 $20$ | $0,1$ | | $10$ | $8$ | 满足 $a_i > a_{i+1}$ 的 $i$ 数量不超过 $20$ | $0,1$ | | $11$ | $12$ | 排列为随机生成 | | | $12$ | $10$ | $n \le 10^5$ | $0,1,5,6$ | | $13$ | $10$ | 无附加限制 | $0,1-12$ |