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
≤ i ≤ j ≤ n*). For each query, determine the
most
frequent value among the integers **a**_{i} , ... , a_{j}.

### Input

The input consists of several test cases.
Each test case starts with a line containing two integers **n**
and **q** (*1 ≤ n, q ≤ 100000*).
The next line contains **n** integers
**a**_{1} , ... , a_{n}
(*-100000 ≤ a*_{i} ≤ 100000, for each *i ∈ {1, ..., n}*)
separated by spaces.
You can assume that for each *i ∈ {1, ..., n-1}: a*_{i} ≤ a_{i+1}.
The following **q** lines contain one query each,
consisting of two integers **i** and **j**
(*1 ≤ i ≤ j ≤ 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.

### Sample Input

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

### Sample Output

1
4
3