# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# A Very Tough Problem

By · Limits 1s, 512 MB

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

InputOutput
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

### Statistics

64% Solution Ratio

foyaz05Earliest, May '18

dip_BRURFastest, 0.2s

foyaz05Lightest, 2.8 MB

NirjhorShortest, 1353B