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
harsha_1_2: 2020-04-19 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 non-negative value using square root decomposition. Complexity is ((q+n)*sqrt(n)). Getting TLE!! Need help

amrit5: 2020-04-18 18:14:00

wrong ans after testcase 9 mos+binary search : (

sagarthecoder: 2019-10-29 18:17:52

I solved it using MO_algorithm &( binary search for per query ).
Be alert for negative frequency when adding or removing. I got 7 times ( RE & WA) for that issue.

huynhtuan71ti: 2019-08-31 18:02:49

Mo's algorithm and binary search -> AC

DOT: 2018-08-01 21:30:34

Mo's Algorithm works. :)

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


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.