시간 제한메모리 제한제출정답맞은 사람정답 비율
1.2 초 (추가 시간 없음) 1024 MB311814219.905%

문제

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

Given a list of 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 to be 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.

예제 입력 1

5 3
2 1 2 1 1
1 2
1 4
1 5

예제 출력 1

2
2
1

예제 입력 2

6 3
3 8 3 2 5 2
1 6
2 4
4 6

예제 출력 2

3
8
2