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
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 

aakash_s:
20151229 17:18:04
wrong answer after 8 test cases !!


Petar Bosnjak:
20151212 22:37:43
Too strict time limit, O(N*sqrt(N)*log(N)) doesn't pass


Philip:
20150525 22:06:50
Very tight time limit...in my case cout vs printf made the difference (and that was after ios_base::sync_with_stdio(false) and cin.tie(0)). I doubt O(N*sqrt(N)*log(N)) will pass mine was O(N^1.5). 

Aditya Paliwal:
20150317 23:33:31
Will O(N*sqrt(N)*log(N)) pass? Last edit: 20150318 14:20:57 
Added by:  Dominik Gleich 
Date:  20110620 
Time limit:  0.100s0.453s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  My own problem. 