题目描述

译自 ROI 2025 Day2 T4. Жизнь программистов

一部关于程序员生活的全新电视剧即将在天狼星电视台播出！这部剧共有 $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$。

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

提示

样例解释 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$ 是样例。