FREQ2  Most Frequent Value
You are given a sequence of n integers a_{0}, a_{1} ... a_{n1}. You are also given several queries consisting of indices i and j (0 ≤ i ≤ j ≤ n1). For each query, determine the number of occurrences of the most frequent value among the integers a_{i} ... a_{j}.
Input
First line contains two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a_{0} ... a_{n1} (0 ≤ a_{i} ≤ 100000, for each i ∈ {0 ... n1}) separated by spaces. The following q lines contain one query each, consisting of two integers i and j (0 ≤ i ≤ j ≤ n1), which indicates the boundary indices for the query.
Output
For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.
Example
Input:
5 3
1 2 1 3 3
0 2
1 2
0 4 Output: 2
1
2
NOTE  This problem is similar to a problem Frequent values.
hide comments
soumyo001:
20221219 20:59:39
can we use segment tree? 

tarun_28:
20210722 08:47:52
Mo's algorithm + Frequency of frequency array:) 

harsha_1_2:
20200419 09:16:51
I am maintaining an array (a) which stores the number of elements for each frequency i.e a[x] is the no of elements having frequency x. I am finding maximum x having a nonnegative value using square root decomposition. Complexity is ((q+n)*sqrt(n)). Getting TLE!! Need help 

amrit5:
20200418 18:14:00
wrong ans after testcase 9 mos+binary search : ( 

sagarthecoder:
20191029 18:17:52
I solved it using MO_algorithm &( binary search for per query ).


huynhtuan71ti:
20190831 18:02:49
Mo's algorithm and binary search > AC 

DOT:
20180801 21:30:34
Mo's Algorithm works. :) 

mahmud2690:
20170730 15:13:41
Too strict time limit 

adityaghosh96:
20170103 04:50:50
O(N * sqrt(N)) with scanf,printf 

erdenebayr_d:
20160309 15:10:11
O(N * sqrt(N)) is passed 
Added by:  Dominik Gleich 
Date:  20110620 
Time limit:  0.100s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  My own problem. 