seuOJ361 - 达达开

题目描述

战神达达开准备参加一场武艺选拔。

选拔一共有 nn 个选手（包括达达开本人），分为 mm 轮。

每一个选手都有一个武艺值，保证所有人的武艺值是 0∼n−10\sim n-1 的排列。

每一轮所有的选手排成一排，按照位置将所有人从 0∼n−10\sim n-1 编号。

然后编号 ∈[li,ri]\in [l_i,r_i] 的选手进行一场武艺比试，武艺值最高的人获胜，其余参赛选手被踢出队伍，所有剩余的选手相对位置不变并从 00 开始 重新编号。

现在其他的 n−1n-1 个人都已经排好了，但是达达开用强硬的手段抓住了自己的未来。

在第一轮开始前，他可以随意地插入现有的队伍中的任意一个位置。

现在他想知道，一开始他站在哪里，能够赢得最多轮武艺选拔。

注意，他必须参加了这一轮的武艺选拔（即在 [li,ri][l_i,r_i] 中），并且获胜，才算赢得这一轮的选拔。

输入格式

第一行三个整数 n,m,xn,m,x，表示选手数量，战斗数量，以及达达开的武艺值。

然后 n−1n-1 行表示其他选手的武艺值，一开始它们已经排成一排。

然后 mm 行，每行两个数 li,ril_i,r_i ，表示第 ii 轮武艺选拔。

输出格式

输入一行一个数，表示一开始达达开所在位置的编号。如果有多个这样的编号，输出最小的一个。

样例

样例输入

5 3 3
1
0
2
4
1 3
0 1
0 1

样例输出

1

样例解释

开始时所有人的武力值依次为 [1,3,0,2,4]
第一次比赛的参赛选手武力值为[3,0,2]，达达开获胜，剩余选手重新排队，武力值依次为[1,3,4]
第二次比赛的参赛选手武力值为[1,3]，达达开获胜，剩余选手重新排队，武力值依次为[3,4]
第三次比赛的参赛选手武力值为[3,4],达达开失败。
可以证明这是样例数据的最佳策略。

数据范围与提示

n≤105,0≤li<ri<nn\leq 10^5,0\leq l_i<r_i<n，保证所有选手的武艺值恰好是 0∼n−10\sim n-1 的排列，每一轮选拔都能正常进行。