19412번 - Hacker Cups and Balls 다국어

문제

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

There are $n$ cups and $n$ balls, both are numbered 1,ドル 2, \ldots, n$. At each moment of time, there is exactly one ball in each cup. Initially, $a_i$-th ball is placed in the $i$-th cup. Admenoor will perform $m$ magic operations on these balls and cups. The $i$-th operation will sort all the balls in the cups numbered between $l_i$ and $r_i,ドル inclusive. The sorting could be performed in either ascending order or descending order. After these $m$ operations, you need to answer which ball is placed in the center cup. We guarantee that $n$ will be 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$ would become $[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$ would become $[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 will sort that balls in ascending order in this operation; otherwise, the balls will be 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$

힌트