Frequent Values

You are given a sequence of $n$ integers $a_1, a_2, \ldots, a_n$ in non-decreasing order. You are also given several queries, each consisting of two indices $i$ and $j$ ($1 \le i \le j \le n$). For each query, determine how many times the most frequent value occurs among $a_i, a_{i+1}, \ldots, a_j$.

The input consists of several test cases. Each test case begins with a line containing two integers $n$ and $q$ ($1 \le n, q \le 100000$). The next line contains $n$ integers $a_1, \ldots, a_n$ ($-100000 \le a_i \le 100000$) separated by spaces. It is guaranteed that $a_i \le a_{i+1}$ for every $i \in \{1, \ldots, n-1\}$. The following $q$ lines each contain one query, given as two integers $i$ and $j$ ($1 \le i \le j \le n$) denoting the boundary indices of the query.

The last test case is followed by a line containing a single $0$.

For each query, print on its own line a single integer: the number of occurrences of the most frequent value within the given range.