Most Frequent in a Slice

Difficulty: 2300 6000 ms 128 MB

offline

Answer Q queries (l, r): the highest frequency of any single value in a_l..r (the count of the mode).

Input: the first line has N and Q; the second line has the array; the next Q lines have l and r.

Output: one line per query with the mode's frequency.

Constraints:

• 1 ≤ N, Q ≤ 10⁵ (tests use N, Q ≤ 1500)
• 1 ≤ a_i ≤ 10⁹

Sample Tests

5 2
1 2 2 3 2
1 3
2 5

2
3

1 1
7
1 1

1

Read the Editorial