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
0

Sample Output

1
4
3

A naive algorithm may not run in time!

Added by:Adrian Kuegel
Date:2007-07-06
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

hide comments
2018-05-18 18:06:37
Thought my submission would give tle as i used map in query
but AC in one go :D
2018-04-13 21:48:46
AC in one go!!!
2018-03-23 14:12:24
someone pls explain the code on codechef link
https://discuss.codechef.com/questions/124793/help-in-understanding-segment-tree-merge-function-of-spoj-frequent-question
2018-03-04 07:53:43
There are multiple test cases! Cost me one WA! :( Btw segment tree rocks! :D
2017-08-04 01:09:25
AC in one go.... ;)
2017-07-20 05:07:35
Dont miss taking test cases... costed me a wrong submission
2017-06-20 12:30:56
getting tle with mo's any comments (anyone who did it with mo's) ?
2017-06-18 18:54:01
Very good question
Try GSS1 first
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).
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.