Couriers

Byteasar works for BAJ, a company that sells computer games. BAJ has contracts with several courier companies, and they deliver the games BAJ sells to its customers. Byteasar is checking how those contracts are being kept. He has a log of the packages BAJ shipped, in chronological order, with the number of the courier company that delivered each package.

If one courier company delivered more than half of the packages shipped during some period, we say that it dominated that period. Byteasar wants to know, for each period he is interested in, whether a courier company dominated it, and which one.

Write a program that finds the dominating courier company for each period, or reports that there is none.

The first line contains two integers $n$ and $m$, separated by a single space ($1 \le n, m \le 500\,000$): the number of packages BAJ shipped and the number of periods to examine. The courier companies are numbered from $1$ to at most $n$.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$, separated by single spaces ($1 \le p_i \le n$). The value $p_i$ is the number of the courier company that delivered the $i$-th package in shipment order.

Each of the next $m$ lines describes one period with two integers $a$ and $b$, separated by a single space ($1 \le a \le b \le n$). The period runs from the $a$-th shipped package to the $b$-th shipped package, both included.

Print one line per period, $m$ lines in total. Each line holds the number of the courier company that dominated the corresponding period, or $0$ if no company dominated it.