Cups and Marbles

Hongjun and Myungwoo like to play. Bored one day, Hongjun invented the following game.

There are $n$ cups and $n$ marbles, each numbered from 1 to $n$. Hongjun put one marble into every cup and lined the cups up in order of their numbers. At the start, cup $i$ holds marble $a_i$.

Hongjun casts a spell $m$ times. One cast takes every cup lying between two chosen cups, sorts the marbles in those cups by number in ascending or descending order, and puts them back one per cup, starting from the lowest numbered cup.

Once every spell is done, Hongjun asks Myungwoo which marble sits in cup $\frac{n+1}{2}$. $n$ is always odd.

Consider $n = 5$, $m = 2$ and $a = [5, 1, 4, 2, 3]$. If the first spell sorts the marbles in cups 1 through 4 in ascending order, $a$ becomes $[1, 2, 4, 5, 3]$. If the second spell sorts the marbles in cups 2 through 5 in descending order, $a$ becomes $[1, 5, 4, 3, 2]$. Cup 3 is left holding marble 4.

Help Myungwoo and write a program that answers Hongjun's question.

The first line contains two integers $n$ and $m$. ($1 \le n \le 99{,}999$, $0 \le m \le 100{,}000$) $n$ is odd.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$. ($1 \le a_i \le n$) $a$ is a permutation of $1$ through $n$.

Each of the next $m$ lines holds one spell, in the order Hongjun casts them. A line contains two integers $l_i$ and $r_i$. ($1 \le l_i, r_i \le n$) If $l_i < r_i$, the marbles in cups $l_i$ through $r_i$ are sorted by number in ascending order. If $l_i \ge r_i$, the marbles in cups $r_i$ through $l_i$ are sorted by number in descending order.

Print the number of the marble in cup $\frac{n+1}{2}$ after all $m$ spells.