A Very Tough Problem

Now-a-days life is very Toph and you need to face a lot of Toph problems. Here is another problem like that. Can you solve it?

You will be given an array of N integers and Q queries. In each query, you will be given L and R. You have to report the output of the following function:

Frequency[] = {0}
minVal = +INF
maxVal = -INF

For i from L to R
    C = A[i]
    Frequency[C] = Frequency[C] + 1
End For

For i from L to R
    C = A[i]
    minVal = MIN(minVal, Frequency[C])
    maxVal = MAX(maxVal, Frequency[C])
End For

Return maxVal - minVal 

Input

The first line will contain two integers N and Q.

Following line will contain N integers A1, A2, ... , An denoting the values of the array.

Next Q lines will contain 2 integers each, denoting L and R.

• 1 ≤ N, Q, Ai ≤ 105
• 1 ≤ L ≤ R ≤ N

Output

For each query, output the required answer.

Sample

Input	Output
10 7 1 2 3 2 3 4 2 5 1 7 1 2 1 3 2 4 2 5 2 6 2 7 1 10	0 0 1 0 1 2 2