해커 컵과 공

Dreamoon의 어두운 면인 Ademnoor가 여러분과 재미있는 게임을 하려고 한다. "컵과 공" 게임을 들어 본 적이 있는가? 여기 그 게임의 해커 버전이 있다!

$n$개의 컵과 $n$개의 공이 있고, 둘 다 $1, 2, \ldots, n$으로 번호가 매겨져 있다. 어느 순간에도 각 컵에는 공이 정확히 하나씩 들어 있다. 처음에는 $i$번째 컵에 $a_i$번째 공이 들어 있다. Admenoor는 이 공과 컵에 $m$번의 마법 연산을 수행한다. $i$번째 연산은 $l_i$번부터 $r_i$번까지의 컵에 들어 있는 모든 공을 정렬한다. 정렬은 오름차순 또는 내림차순으로 이루어질 수 있다. 이 $m$번의 연산이 끝난 뒤, 가운데 컵에 들어 있는 공이 무엇인지 답해야 한다. $n$은 홀수임이 보장되므로, 가운데 컵은 $\frac{n + 1}{2}$번째 컵을 뜻한다.

예를 들어 $n = 5$, $m = 2$, $a = [5, 1, 4, 2, 3]$인 경우를 보자. 첫 번째 연산이 $1$번부터 $4$번까지의 컵에 들어 있는 공을 오름차순으로 정렬하는 것이라면 $a$는 $[1, 2, 4, 5, 3]$이 된다. 두 번째 연산이 $2$번부터 $5$번까지의 컵에 들어 있는 공을 내림차순으로 정렬하는 것이라면 $a$는 $[1, 5, 4, 3, 2]$가 된다. 이 예에서 모든 연산이 끝난 뒤 가운데 컵에 들어 있는 공의 번호는 $4$이다.

첫 번째 줄에 두 정수 $n$과 $m$이 주어진다. 다음 줄에 $n$개의 정수 $a_1, a_2, \ldots, a_n$이 주어진다. 이어지는 $m$개의 줄에는 각각 두 정수 $l_i$와 $r_i$가 주어진다. $l_i < r_i$이면 Admenoor는 이번 연산에서 공을 오름차순으로 정렬하고, 그렇지 않으면 내림차순으로 정렬한다.

모든 연산이 끝난 뒤 가운데 컵에 들어 있는 공의 번호를 한 줄에 출력한다.

• $1 \le n \le 99\,999$
• $n$은 홀수이다
• $0 \le m \le 10^5$
• $1 \le a_i \le n$
• $\langle a_i \rangle$는 $1, 2, \ldots, n$의 순열이다
• $1 \le l_i, r_i \le n$