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.


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.

hide comments
2015-12-29 17:18:04
wrong answer after 8 test cases !!
2015-12-12 22:37:43 Petar Bosnjak
Too strict time limit, O(N*sqrt(N)*log(N)) doesn't pass
2015-05-25 22:06:50 Philip
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).
2015-03-17 23:33:31 Aditya Paliwal
Will O(N*sqrt(N)*log(N)) pass?

Last edit: 2015-03-18 14:20:57
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.