题目描述

给定 $1\sim n$ 的排列 $p_1\sim p_n$。

对 $p$ 施加 $q$ 次操作，第 $i$ 次操作给定 $l_i,r_i$，表示：

• 令 $S=\{p_{l_i},\ldots,p_{r_i}\}$；
• 对于 $j=0,1,\ldots,r_i-l_i$，执行以下步骤：
  • 若 $j$ 为偶数，令 $v=\min S$；否则令 $v=\max S$。
  • 令 $p_{j+l_i}\gets v$，$S\gets S\backslash \{v\}$（即从 $S$ 中删去 $v$）。

给定正整数 $m$。求出 $q$ 次操作完后数字 $m$ 的位置。

输入格式

第一行，三个正整数 $n,q,m$（$1\le n,q\le 10^5$，$1\le m\le n$）。

第二行，$n$ 个正整数 $p_1,\ldots,p_n$。

接下来 $q$ 行，第 $i$ 行两个正整数 $l_i,r_i$（$1\le l_i\le r_i\le n$）。

输出格式

输出一行一个正整数，表示操作完后数字 $m$ 的位置。

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

5

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

2

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

7

提示

样例解释

样例一解释：

• 第一次操作完后，$p=[4,2,3,1,7,5,6]$；
• 第二次操作完后，$p=[4,2,1,7,3,5,6]$；
• 第三次操作完后，$p=[1,7,2,4,3,5,6]$。

数字 $3$ 的位置为 $5$。

子任务