빈번한 값

$n$개의 정수로 이루어진 수열 $a_1, a_2, \ldots, a_n$이 비내림차순으로 정렬되어 주어진다. 또한 두 인덱스 $i$와 $j$ ($1 \le i \le j \le n$)로 이루어진 질의가 여러 개 주어진다. 각 질의마다 부분 수열 $a_i, a_{i+1}, \ldots, a_j$ 안에서 가장 자주 등장하는 값이 몇 번 나타나는지 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $n$과 $q$ ($1 \le n, q \le 100000$)가 주어진다. 다음 줄에는 $n$개의 정수 $a_1, \ldots, a_n$ ($-100000 \le a_i \le 100000$)이 공백으로 구분되어 주어진다. 모든 $i \in \{1, \ldots, n-1\}$에 대해 $a_i \le a_{i+1}$임이 보장된다. 이어지는 $q$개의 줄에는 각각 하나의 질의가 주어지며, 질의의 경계 인덱스를 나타내는 두 정수 $i$와 $j$ ($1 \le i \le j \le n$)로 이루어진다.

마지막 테스트 케이스 다음에는 정수 $0$ 하나만 있는 줄이 주어진다.

각 질의마다 주어진 구간에서 가장 자주 등장하는 값의 등장 횟수를 한 줄에 하나씩 정수로 출력한다.