Given a non-decreasing series of integers a₁, a₂ ... a_n and indices 1 ≤ i ≤ j ≤ n, what is the maximum number of repeated numbers within a_i, a_i+1 ... a_j?

Input

Input contains several test cases.

Each case begins with two integers 1 ≤ n, q ≤ 10⁵.

Next line contains n integers (a₁, a₂ ... a_n), each one having a size of lower than or equal to 10⁵.

In next q lines, there are queries. Each one contains two integers 1 ≤ i ≤ j ≤ n.

Input terminates when n, q are zero.

Output

For each query, print the maximum number of repetitions within numbers a_i, a_i+1 ... a_j.

Example

Input:
10 3
1 1 3 3 3 3 5 10 10 10
2 3
1 10
5 10
0 0

Output:
1
4
3