Best Student

The SY School selects a best student every day. Given a list of the best students for $n$ days, the school wants to know which student was selected as the best student most often during a period $[S, E]$ of days from $S$ to $E$. The school plans to award that student a gift.

Given a list of the best students for $n$ consecutive days and $q$ queries $\{(S_1, E_1), \dots, (S_q, E_q)\}$, write a program to find the best student selected most often during the period $[S_i, E_i]$ for each query $(S_i, E_i)$.

Your program is to read from standard input. The input starts with a line containing two integers, $n$ and $q$, representing the number of days and the number of queries, respectively, where $1 \le n \le 100,000$ and $1 \le q \le 100,000$. Students have unique id numbers between $1$ and $10^9$. The next line consists of $n$ positive integers representing $n$ id numbers for best students, ordered from day $1$ to day $n$. Each of the following $q$ lines consists of two positive integers, $S_i$ and $E_i$, that represent a query $(S_i, E_i)$, where $[S_i, E_i]$ is the period of days from $S_i$ to $E_i$. Note that $1 \le S_i \le E_i \le n$ for $i = 1, \dots, q$.

Your program is to write to standard output. Print exactly $q$ lines. The $i$-th line should contain the id number of the student selected most often as best student during the $i$-th period $[S_i, E_i]$. When there are more than one such students, the program should print the largest one among their id numbers.