FREQ2 - Most Frequent Value
You are given a sequence of n integers a0, a1 ... an-1. You are also given several queries consisting of indices i and j (0 ≤ i ≤ j ≤ n-1). For each query, determine the number of occurrences of the most frequent value among the integers ai ... aj.
Input
First line contains two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a0 ... an-1 (0 ≤ ai ≤ 100000, for each i ∈ {0 ... n-1}) separated by spaces. The following q lines contain one query each, consisting of two integers i and j (0 ≤ i ≤ j ≤ n-1), 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
aakash_s:
2015-12-29 17:18:04
wrong answer after 8 test cases !!
|
|
Petar Bosnjak:
2015-12-12 22:37:43
Too strict time limit, O(N*sqrt(N)*log(N)) doesn't pass
|
|
Philip:
2015-05-25 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:
2015-03-17 23:33:31
Will O(N*sqrt(N)*log(N)) pass? Last edit: 2015-03-18 14:20:57 |
Added by: | Dominik Gleich |
Date: | 2011-06-20 |
Time limit: | 0.100s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | My own problem. |