Hacker Cups and Balls

The dark side of Dreamoon, Ademnoor, wants to play an interesting game with you. Have you heard of the game "cups and balls"? Here is the hacker version of it!

There are $n$ cups and $n$ balls, both numbered $1, 2, \ldots, n$. At every moment, each cup holds exactly one ball. Initially, the $a_i$-th ball is placed in the $i$-th cup. Admenoor performs $m$ magic operations on these balls and cups. The $i$-th operation sorts all the balls in the cups numbered between $l_i$ and $r_i$, inclusive. The sorting can be done in ascending order or descending order. After these $m$ operations, you must answer which ball is placed in the center cup. We guarantee that $n$ is an odd integer, so the center cup means the $\frac{n + 1}{2}$-th cup.

For example, consider $n = 5$, $m = 2$ and $a = [5, 1, 4, 2, 3]$. If the first operation is to sort the balls in the cups numbered between $1$ and $4$ in ascending order, then $a$ becomes $[1, 2, 4, 5, 3]$. If the second operation is to sort the balls in the cups numbered between $2$ and $5$ in descending order, then $a$ becomes $[1, 5, 4, 3, 2]$. In this example, the number of the ball in the center cup after all operations is $4$.

The first line of input contains two integers $n$ and $m$. The following line contains $n$ integers $a_1, a_2, \ldots, a_n$. Each of the following $m$ lines contains two integers $l_i$ and $r_i$. If $l_i < r_i$, Admenoor sorts the balls in ascending order in this operation; otherwise, the balls are sorted in descending order in this operation.

Output a single line with the number of the ball in the center cup after all operations.

• $1 \le n \le 99\,999$
• $n$ is an odd integer
• $0 \le m \le 10^5$
• $1 \le a_i \le n$
• $\langle a_i \rangle$ is a permutation of $1, 2, \ldots, n$
• $1 \le l_i, r_i \le n$