大学的第一学期即将结束。Marin 决定去上体育课，以凑齐他的第 12 次出勤，从而通过这门课程。但他被体育馆前排队的学生人数震惊到了。

他数了数，包括他自己在内一共有 $n$ 名学生，并发现了一个有趣的规律：没有任意两名学生的身高相同，且对于 $1$ 到 $n$ 之间的每个整数，都恰好有一名学生是这个身高。

在课程开始前，学生们排成了一排。从左到右观察，队伍中学生的身高构成了大小为 $n$ 的排列 $p$。老师对队伍中学生的顺序有一些奇特的要求，因此他决定发布 $q$ 个命令，且必须按给定的顺序执行。

每个命令的形式为 $l_i$ $r_i$，表示位置从 $l_i$ 到 $r_i$（含）的学生需要出列，然后按以下方式填补空缺的位置：

• 位置 $l_i$ 由出列学生中最矮的学生填补。
• 位置 $l_i + 1$ 由剩余学生中最高的学生填补。
• 位置 $l_i + 2$ 再次由剩余学生中最矮的学生填补。
• 位置 $l_i + 3$ 由剩余学生中最高的学生填补。
• 依此类推，在最矮和最高之间交替，直到位置 $r_i$ 被填满。

在执行完所有命令后，Marin 不再确定自己是否站在正确的位置，或者他是否在某个时刻走错了地方。然而，他记得初始排列 $p$、所有 $q$ 个命令的给出顺序，并且他已经告诉你他的身高 $m$。他请求你帮他确定他应该站在哪个位置。

输入格式

第一行包含三个自然数 $n, q, m$（$1 \le n, q \le 10^5$，$1 \le m \le n$），即题目描述中的参数。

第二行包含一个长度为 $n$ 的序列，表示排列 $p$（$1 \le p_i \le n$）。

接下来的 $q$ 行，每行包含两个数 $1 \le l_i \le r_i \le n$，表示第 $i$ 个命令。

输出格式

在第一行也是唯一的一行中，输出一个整数——Marin 应该占有的位置。

子任务

样例

输入样例 1

7 3 3
4 2 3 7 1 6 5
4 7
3 5
1 4

输出样例 1

5

输入样例 2

6 4 1
5 3 6 2 1 4
2 4
3 5
2 6
5 6

输出样例 2

2

输入样例 3

8 2 5
8 7 6 5 4 3 1 2
2 8
1 7

输出样例 3

7

说明

样例 1 解释

在执行第一个命令后，队伍中学生的身高为：4 2 3 1 7 5 6。 在执行第二个命令后，身高为：4 2 1 7 3 5 6。 最后，在执行第三个命令后，队伍应该看起来像这样：1 7 2 4 3 5 6。 Marin 的身高为 $3$，因此他应该占有从左数起第 $5$ 个位置。