컵과 구슬

홍준이와 명우는 노는 것을 좋아한다. 심심하던 홍준이가 다음 놀이를 생각해냈다.

1번부터 $n$번까지 서로 다른 번호가 붙은 컵 $n$개와 구슬 $n$개가 있다. 홍준이는 컵마다 구슬을 하나씩 넣고 컵의 번호 순서대로 일렬로 놓았다. 처음에 $i$번 컵에는 $a_i$번 구슬이 들어 있다.

홍준이는 마법을 $m$번 쓴다. 마법을 한 번 쓰면 지정한 두 컵 사이에 놓인 모든 컵의 구슬을 번호 오름차순 또는 내림차순으로 정렬해서, 번호가 가장 작은 컵부터 차례로 하나씩 다시 담는다.

마법을 모두 쓰고 나면 홍준이는 명우에게 $\frac{n+1}{2}$번 컵에 몇 번 구슬이 있는지 묻는다. $n$은 항상 홀수다.

$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]$가 된다. 3번 컵에는 4번 구슬이 남는다.

명우를 도와 홍준이의 질문에 답하는 프로그램을 작성하자.

첫째 줄에 두 정수 $n$과 $m$이 주어진다. ($1 \le n \le 99{,}999$, $0 \le m \le 100{,}000$) $n$은 홀수다.

둘째 줄에 $n$개의 정수 $a_1, a_2, \dots, a_n$이 주어진다. ($1 \le a_i \le n$) $a$는 $1$부터 $n$까지의 순열이다.

셋째 줄부터 $m$개의 줄에 홍준이가 쓰는 마법이 순서대로 주어진다. 각 줄에는 두 정수 $l_i$와 $r_i$가 있다. ($1 \le l_i, r_i \le n$) $l_i < r_i$이면 $l_i$번 컵부터 $r_i$번 컵까지의 구슬을 번호 오름차순으로 정렬하고, $l_i \ge r_i$이면 $r_i$번 컵부터 $l_i$번 컵까지의 구슬을 번호 내림차순으로 정렬한다.

마법을 $m$번 모두 쓴 뒤 $\frac{n+1}{2}$번 컵에 있는 구슬의 번호를 출력한다.