최고의 학생

SY 학교는 매일 최고의 학생을 한 명 선정한다. $n$일 동안의 최고의 학생 목록이 주어졌을 때, 학교는 $S$일부터 $E$일까지의 기간 $[S, E]$ 동안 최고의 학생으로 가장 많이 선정된 학생이 누구인지 알고 싶어 한다. 학교는 그 학생에게 상을 줄 계획이다.

$n$일 연속의 최고의 학생 목록과 $q$개의 질의 $\{(S_1, E_1), \dots, (S_q, E_q)\}$가 주어질 때, 각 질의 $(S_i, E_i)$에 대해 기간 $[S_i, E_i]$ 동안 가장 많이 선정된 최고의 학생을 구하는 프로그램을 작성하시오.

입력은 표준 입력에서 읽는다. 입력의 첫 줄에는 두 정수 $n$과 $q$가 주어지며, 각각 날짜의 수와 질의의 수를 나타낸다. 여기서 $1 \le n \le 100,000$이고 $1 \le q \le 100,000$이다. 학생들은 $1$부터 $10^9$ 사이의 서로 다른 id 번호를 가진다. 다음 줄에는 $n$개의 양의 정수가 주어지며, $1$일부터 $n$일까지 순서대로 최고의 학생의 id 번호 $n$개를 나타낸다. 이어지는 $q$개의 각 줄에는 두 양의 정수 $S_i$와 $E_i$가 주어지며, 질의 $(S_i, E_i)$를 나타낸다. 여기서 $[S_i, E_i]$는 $S_i$일부터 $E_i$일까지의 기간이다. $i = 1, \dots, q$에 대해 $1 \le S_i \le E_i \le n$이다.

출력은 표준 출력에 쓴다. 정확히 $q$줄을 출력한다. $i$번째 줄에는 $i$번째 기간 $[S_i, E_i]$ 동안 최고의 학생으로 가장 많이 선정된 학생의 id 번호를 출력한다. 그러한 학생이 둘 이상이면, 그중 id 번호가 가장 큰 학생을 출력한다.