一个新的关于程序员生活的系列剧包含 $n$ 集，编号从 $1$ 到 $n$。Sirius TV 电视台计划在 $k$ 天内按顺序播放这些剧集，每天播放由一集或多集连续剧集组成的片段。每一集都将恰好被播放一次。

根据试映结果，公司市场部为剧集制定了评分：第 $i$ 集被赋予一个 $1$ 到 $n$ 之间的整数 $a_i$，最有趣的剧集评分为 $1$，最无聊的剧集评分为 $n$。不同剧集的评分各不相同，因此数字 $[a_1, a_2, \dots, a_n]$ 构成了一个排列。

假设已经决定了哪一天播放哪些剧集。对于每一天，我们定义该天的评分为当天最无聊剧集的评分。换句话说，如果在第 $j$ 天播放从 $l_j$ 到 $r_j$ 的剧集，那么该天的评分 $b_j$ 等于 $[a_{l_j}, a_{l_j+1}, \dots, a_{r_j}]$ 中的最大值。

为了使剧集播放成功，需要吸引观众观看。在所有将剧集划分为 $k$ 个片段（按天）的可能方式中，必须选择一种使得第一天的评分尽可能好：即 $b_1$ 最小。在这些方式中，依次最小化第二天的评分 $b_2$，在选定 $b_1$ 和 $b_2$ 的情况下最小化 $b_3$，以此类推。因此，需要将剧集划分为 $k$ 个片段，使得序列 $[b_1, b_2, \dots, b_k]$ 字典序最小。

你需要回答 $q$ 个查询，每个查询由两个数字 $k$ 和 $i$ 给出。作为查询的回答，你需要输出 $b_i$ 的值，即在 $k$ 天播放剧集的最佳方案中第 $i$ 天的评分。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \leqslant n, q \leqslant 300\,000$)，分别表示剧集数量和查询数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \leqslant a_i \leqslant n$)，表示剧集的评分。保证数组 $a$ 是 $1$ 到 $n$ 的整数排列。

接下来的 $q$ 行，每行包含两个整数 $k$ 和 $i$ ($1 \leqslant i \leqslant k \leqslant n$)，表示相应查询的参数。

输出格式

输出 $q$ 行，每行对应一个查询的答案，顺序与输入中的查询顺序一致。

样例

输入格式 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$。

子任务