Migrated from Lutece 382 Frequent values

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

You are given a sequence of $n$ integers $a_1, a_2,\cdots , a_n$ in non-decreasing order. In addition to that, you are given several queries consisting of indices $i$ and $j$ ($1\leq i\leq j\leq n$). For each query, determine the most frequent value among the integers $a_i ,\cdots , a_j$.

Input

The input consists of several test cases. Each test case starts with a line containing two integers $n$ and $q$ ($1\leq n, q\leq 100000$). The next line contains $n$ integers $a_1 , \cdots , a_n$ ($-100000\leq a_i\leq 100000$, for each $i\in [1, \cdots, n]$) separated by spaces. You can assume that for each $i \in [1, \cdots, n-1]: a_i \leq a_{i+1}$. The following $q$ lines contain one query each, consisting of two integers $i$ and $j$ ($1\leq i\leq j\leq n$), which indicate the boundary indices for the query.

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

Output

For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.

Samples

10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0

1
4
3

Resources

Ulm Local 2007