FREQUENT - Frequent values

You are given a sequence of n integers a1 , a2 , ... , an in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers ai , ... , aj.

Input Specification

The input consists of several test cases. Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a1 , ... , an (-100000 ≤ ai ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: ai ≤ ai+1. The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the query.

The last test case is followed by a line containing a single 0.

Output Specification

For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.

Sample Input

10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10

Sample Output


A naive algorithm may not run in time!

hide comments
coolio_1: 2018-03-04 07:53:43

There are multiple test cases! Cost me one WA! :( Btw segment tree rocks! :D

abhishek18620: 2017-08-04 01:09:25

AC in one go.... ;)

aman2309: 2017-07-20 05:07:35

Dont miss taking test cases... costed me a wrong submission

praney_rai: 2017-06-20 12:30:56

getting tle with mo's any comments (anyone who did it with mo's) ?

dhrv_shrma04: 2017-06-18 18:54:01

Very good question
Try GSS1 first

sonudoo: 2017-06-16 17:01:07

I don't comment often. But after solving this. Yes, AC in one go. I only stored one integer in each node of the segment tree (the maximum frequency value) and used that fact that apart from the maximum of left and right child, only one more thing can contribute to maximum in the combined range (and that thing is the frequency of 'mid' and 'mid+1' element, if they are equal).

mkfeuhrer: 2017-05-29 20:38:23

one go AC - MO's , used priority queue for inc , dec and max freq !!

Last edit: 2017-05-29 20:39:11
sfialok98: 2017-05-26 22:34:16

First problem on Segment tree,all by myself...
AC in one go... :-)

rishi_07: 2017-03-05 00:19:17

Nice Question. AC in one go!

Last edit: 2017-03-05 00:19:48
vladimira: 2017-02-14 21:23:07

Yippee! Accepted with python 2.6 (PyPy)
According to this benchmark
python 3 (together with ruby) is 15-20 slower than c++
and thats why I couldnt break time limit
But PyPy was my savior.
0.5 secs I guess its not that bad considering that best results with c++ are about 0.1 secs

Last edit: 2017-02-15 12:32:09

Added by:Adrian Kuegel
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:University of Ulm Local Contest 2007