Problem Description

You are given a permutation $p_1 \sim p_n$ of $1 \sim n$.

Apply $q$ operations to $p$. In the $i$-th operation, you are given $l_i, r_i$, meaning:

• Let $S = \{p_{l_i}, \ldots, p_{r_i}\}$.
• For $j = 0, 1, \ldots, r_i - l_i$, perform the following steps:
  • If $j$ is even, let $v = \min S$; otherwise, let $v = \max S$.
  • Set $p_{j + l_i} \gets v$, and update $S \gets S \backslash \{v\}$ (that is, remove $v$ from $S$).

Given a positive integer $m$, find the position of the number $m$ after all $q$ operations.

Input Format

The first line contains three positive integers $n, q, m$ ($1 \le n, q \le 10^5$, $1 \le m \le n$).

The second line contains $n$ positive integers $p_1, \ldots, p_n$.

The next $q$ lines each contain two positive integers $l_i, r_i$ ($1 \le l_i \le r_i \le n$).

Output Format

Output one positive integer in a single line, representing the position of the number $m$ after all operations.

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

Hint

Sample Explanation

Explanation for Sample 1:

• After the first operation, $p = [4,2,3,1,7,5,6]$.
• After the second operation, $p = [4,2,1,7,3,5,6]$.
• After the third operation, $p = [1,7,2,4,3,5,6]$.

The position of the number $3$ is $5$.

Subtasks

Translated by ChatGPT 5