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 IamHot, kitorp · 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

Discussion

Statistics


64% Solution Ratio

foyaz05Earliest, May '18

dip_BRURFastest, 0.2s

foyaz05Lightest, 2.8 MB

NirjhorShortest, 1353B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.