Problems
Frequent values
Frequent values
You are given a sequence of $n$ integers $a_1, a_2, ..., a_n$ in non-decreasing order. In addition to that, you are given several queries consisting of indices $i$ and $j~(1 \le i \le j \le n)$. For each query, determine the most frequent value among the integers $a_i, ..., a_j$.
\InputFile
Consists of several test cases. Each test case starts with a line containing two integers $n$ and $q~(1 \le n, q \le 10^5)$. The next line contains $n$ integers $a_1, a_2, ..., a_n~(-10^5 \le a_i \le 10^5)$. You can assume that for each $i ∈ {1, ..., n - 1}: a_i \le a_{i+1}$. The following $q$ lines contain one query each, consisting of two integers $i$ and $j~(1 \le i \le j \le n)$, which indicate the boundary indices for the query.
The last test case is followed by a line containing a single $0$.
\OutputFile
For each query, print one line with one integer: the number of occurrences of the most frequent value within the given range.
Input example #1
10 3 -1 -1 1 1 1 1 3 10 10 10 2 3 1 10 5 10 0
Output example #1
1 4 3