P15354 [COCI 2025/2026 #4] Physical Education / Tjelesni

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.

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 one positive integer in a single line, representing the position of the number $m$ after all operations.

### 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 | Subtask ID | Score | Constraints | | :-: | :-: | :- | | $1$ | $7$ | $n, q \le 1000$ | | $2$ | $11$ | $l_i = 1$ | | $3$ | $17$ | $m \in \{1,n\}$ | | $4$ | $24$ | $n, q \le 5000$ | | $5$ | $51$ | No additional constraints. | Translated by ChatGPT 5