## 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 31 2 1 3 30 21 20 4

Output:
212NOTE - This problem is similar to a problem Frequent values.```

hide comments
 mahmud2690: 2017-07-30 15:13:41 Too strict time limit adityaghosh96: 2017-01-03 04:50:50 O(N * sqrt(N)) with scanf,printf erdenebayr_d: 2016-03-09 15:10:11 O(N * sqrt(N)) is passed 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-0.453s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64 Resource: My own problem.