P6138 [IOI 2012] 骑马比武竞赛

1491 年公爵 Milan Lodovico Sforza 为了他与 Beatrice d'Este 的婚礼，要求Leonardo 来负责筹备婚礼的庆典。在这个庆典中包含了一个盛大的持续三天的骑马比武竞赛，但是最受欢迎的骑士迟到了... 在一骑马比武的竞赛，$N$ 个骑士一开始被排成一排然后按照他们的位置从 $0$ 到 $N-1$ 开始编号。骑马比武的主持人每一回合叫出两个位置 $S$ 跟 $E$ （其中 $0 \le S < E \le N - 1$）。所有介于 $S$ 与 $E$ （含） 这两个位置的骑士则开始进行骑马比武。最后的赢家可以留下来继续进行竞赛， 并回到他原来的位置，而输家则离开这个竞赛。在这之后，剩下的骑士按照原来排列的顺 序，往前挤掉空出来的位置。所以他们的位置编号变成从 $0$ 到 $N - (E - S) - 1$。骑马比武竞赛的主持人接着进行下一个回合的比赛，直到最后剩下唯一个骑士。 Leonardo 知道所有骑士有不同的强度，这个强度从 $0$ (最弱) 到 $N-1$ (最强)。他也知道骑马比武竞赛的主持人会下怎么样的命令来进行C回合的竞赛，毕竟他是无所不能的 Leonardo。而且他也确定在每一个回合中，拥有最大强度的骑士会获得胜利。 $N$ 个骑士中的 $N-1$ 个骑士已经排成了一排，只是最受欢迎的骑士还未出现。这个骑士的强度为 $R$ 但是他迟到了。为了让这场竞赛达到最高潮, Leonardo 想要让这个骑士能好好展现他的风采，所以想要帮他安插一个位置，而这个位置可以使得这个骑士能获得最多回合的 胜利。请注意，我们不关心与此骑士无关的回合。我们只关心包含此骑士而且由他赢得胜利的回合。 **例子** 假设有 $5$ 个骑士，其中 $4$ 个骑士已经排列好，而他们的强度分别是 $[1,0,2,4]$。而迟到骑士的强度为 $3$ 。假设要进行 $3$ 回合，骑马比武的主持人打算要叫出的位置 $(S,E)$ 分别是 $(1, 3)$，$(0, 1)$，$(0, 1)$。 假设 Leonardo 将迟到的骑士插到第一个位置而且迟到的骑士强度为 $3$。那么骑士强度的排列将会是 $[3, 1, 0, 2, 4]$。第一回合参与的骑士为位置 $1,2,3$ 的骑士，他们的强度分别是 $1,0,2$，所以由强度 $2$ 的骑士获得胜利。经过这一回合，新的骑士强度的排列变成 $[3, 2, 4]]$。下一个回合是由强度 $3$ 与强度 $2$（位置 $0,1$）的骑士进行比赛，由强度 $3$ 的骑士获得胜利。而骑士强度的排列则变成 $[3,4]$。最后一回合（位置 $0,1$）由强度 $4$ 的骑士获得胜利。那么，迟到的骑士只有获得一回合的胜利 (第二回合)。 若 Leonardo 将迟到的骑士插入强度 $1$ 与强度 $0$ 的骑士中间，骑士强度的排列将会是 $[1,3,0,2,4]$。这一次, 第一回合比赛的骑士强度为 $3,0,2$。由强度 $3$ 的骑士获胜，然后骑士强度的排列变成 $[1,3,4]$。在第二回合中由强度 $1$ 对上强度 $3$ 的骑士，由强度 $3$ 的骑士获胜。最后的一回合，骑士强度的排列变成 $[3,4]$，由强度 $4$ 的骑士获得胜利。在这个排列中，迟到的骑士获得两回合的胜利。这实际上是最佳的位置，因为没有其他的位置可以让迟到的骑士获得两回合以上的胜利。 你的任务是写一个程序来帮迟到的骑士选择最佳的位置让他能获得最多的胜利回合数，以符合 Leonardo 的期待。

- 第一行，$3$个整数 $N$，$C$，$R$，其中 $N$ 表示骑士的个数，$C$ 表示竞赛主持人会进行的回合数，$R$ 表示迟到的骑士的强度。 - 第二行，$N$ 个整数 $K[0],K[1],\cdots,K[N-1]$，表示已经排列好成一列的 $N-1$ 个骑士的强度 - 第三行，$2C$ 个整数 $S[0],E[0],S[1],E[1],\cdots,E[N-1],S[N-1]$，对于 $0 \le i \le C-1$，竞赛主持人进行第 $i +1$ 回合比赛的骑士为从位置 $S[i]$ 到位置 $E[i]$ (含). 你可以假设对每一个 $i$ , $S[i] < E[i]$。

共一行，让迟到的骑士能获得最多胜利回合数的位置。如果存在多个最优的位置，输出编号最小的位置。

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$1 \le C \le N-1$，在第 $i+1$ 回合，$E[i]$ 会小于这个回合剩下的骑士数量。经过 $C$ 回合的命令之后，只会剩下一个骑士。