AT_joi2015ho_d 舞踏会 (Ball)

在 IOI 王国，为了庆祝公主 JOI 的生日，将举办一场舞会。 预计有 $N$ 位贵族参加舞会，$N$ 是奇数。每位贵族编号为 $1$ 到 $N$。每位贵族都有一个表示舞蹈水平的整数，对于贵族 $i$（$1 \leq i \leq N$），其舞蹈水平为 $D_i$。 舞会中，包括 JOI 公主在内的 $N+1$ 个人将两两组队跳舞。在 IOI 王国，为了让高水平者能帮助初学者，传统上采用如下方式决定舞伴： - 首先，$N$ 位贵族排成一列。 - 只要队列中人数大于 $1$，重复以下操作： - 查看队列最前面的 $3$ 位贵族的舞蹈水平。 - 在这 $3$ 人中，舞蹈水平最高的贵族记为 $A$。若有多人并列，则取编号最小者为 $A$。 - 在这 $3$ 人中，舞蹈水平最低的贵族记为 $B$。若有多人并列，则取编号最大者为 $B$。 - $A$ 与 $B$ 组成一组并离开队列。 - 剩下的那个人移动到队列末尾。 - 最终剩下的 $1$ 人将与 JOI 公主组队。 对于编号 $1$ 到 $M$（$1 \leq M \leq N-2$）的 $M$ 位贵族，他们在初始队列中的位置已确定。剩下的 $N-M$ 位贵族的排列顺序由国王自由决定。 JOI 公主刚刚学会跳舞，因此国王希望能让与 JOI 公主组队的贵族的舞蹈水平尽可能高。请你求出 JOI 公主最终可能组队的贵族的舞蹈水平的最大值。

从标准输入读取以下数据。 - 第 $1$ 行包含两个整数 $N, M$，表示参加舞会的贵族人数和初始队列中位置已确定的贵族人数。 - 接下来 $M$ 行，第 $i$ 行（$1 \leq i \leq M$）包含两个整数 $D_i, P_i$，表示贵族 $i$ 的舞蹈水平为 $D_i$，且初始时排在队列第 $P_i$ 个位置。 - 接下来 $N-M$ 行，第 $i$ 行（$1 \leq i \leq N-M$）包含一个整数 $D_{i+M}$，表示贵族 $i+M$ 的舞蹈水平为 $D_{i+M}$。

输出一个整数，表示 JOI 公主最终可能组队的贵族的舞蹈水平的最大值。

## 任务 给定每位贵族的舞蹈水平和 $M$ 位贵族的初始队列位置，编写程序求出 JOI 公主最终可能组队的贵族的舞蹈水平的最大值。 ## 限制 所有输入数据满足以下条件： - $3 \leq N \leq 99\,999$。 - $N$ 是奇数。 - $1 \leq M \leq N-2$。 - $1 \leq D_i \leq 1\,000\,000\,000$（$1 \leq i \leq N$）。 - $1 \leq P_i \leq N$（$1 \leq i \leq M$）。 - $P_i \neq P_j$（$1 \leq i < j \leq M$）。 ## 子任务 ### 子任务 1 [8 分] - 满足 $N \leq 9$。 ### 子任务 2 [16 分] - 满足 $N \leq 19$。 ### 子任务 3 [44 分] - 满足 $N \leq 1\,999$。 ### 子任务 4 [32 分] 无额外限制。 ## 样例解释 1 初始时有 $3$ 位贵族的位置已确定。  括号内的数字表示舞蹈水平。左端为队列前端。 例如，若队列顺序为贵族 $5$，贵族 $1$，贵族 $4$，贵族 $6$，贵族 $2$，贵族 $3$，贵族 $7$，则：  所有贵族排好队后的顺序如下： 此时队列变化如下： - 队列前 $3$ 人（贵族 $5$，$1$，$4$）中，舞蹈水平最高的是贵族 $4$，最低的是贵族 $5$，于是 $4$ 和 $5$ 组队，剩下的贵族 $1$ 移到队尾。 - 接着，队列前 $3$ 人（贵族 $6$，$2$，$3$）中，舞蹈水平最高的是贵族 $6$ 和 $3$，取编号较小的贵族 $3$，最低的是贵族 $2$，于是 $3$ 和 $2$ 组队，剩下的贵族 $6$ 移到队尾。 - 接着，队列前 $3$ 人（贵族 $7$，$1$，$6$）中，舞蹈水平最高的是贵族 $7$，最低的是贵族 $1$，于是 $7$ 和 $1$ 组队，剩下的贵族 $6$ 移到队尾。 - 最终只剩贵族 $6$，与 JOI 公主组队。贵族 $6$ 的舞蹈水平为 $8$，这是 JOI 公主可能组队的贵族舞蹈水平的最大值。  队列变化过程示意图。 ## 样例解释 2 无论如何排列，最终都是贵族 $2$ 与 JOI 公主组队。 由 ChatGPT 4.1 翻译