FREQUENT  Frequent values
You are given a sequence of n integers a_{1} , a_{2} , ... , a_{n} in nondecreasing 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 a_{i} , ... , a_{j}.
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 a_{1} , ... , a_{n} (100000 ≤ a_{i} ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n1}: a_{i} ≤ a_{i+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 0
Sample Output
1 4 3
A naive algorithm may not run in time!
hide comments
coolio_1:
20180304 07:53:43
There are multiple test cases! Cost me one WA! :( Btw segment tree rocks! :D 

abhishek18620:
20170804 01:09:25
AC in one go.... ;) 

aman2309:
20170720 05:07:35
Dont miss taking test cases... costed me a wrong submission


praney_rai:
20170620 12:30:56
getting tle with mo's any comments (anyone who did it with mo's) ? 

dhrv_shrma04:
20170618 18:54:01
Very good question


sonudoo:
20170616 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:
20170529 20:38:23
one go AC  MO's , used priority queue for inc , dec and max freq !! Last edit: 20170529 20:39:11 

sfialok98:
20170526 22:34:16
Hurrah..!!


rishi_07:
20170305 00:19:17
Nice Question. AC in one go! Last edit: 20170305 00:19:48 

vladimira:
20170214 21:23:07
Yippee! Accepted with python 2.6 (PyPy)

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