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