2458. Frequent values

输入格式

The input consists of several test cases. Each test case starts with a line containing two integers $n$ and $q$ $(1\le n,q\le 100000)$. The next line contains $n$ integers $a_1,\dots ,a_n$ $(-100000\le a_i\le 100000,\mathrm{\forall }i\in 1,\dots ,n)$ separated by spaces. You can assume that for each $i\in 1,\dots ,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$.

输出格式

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

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

1
4
3