This problem is a Mooshak version of a UVA and SPOJ problem.

[PC016] Frequent Values

You are given a sequence of \(n\) integers \(a_1, a_2 , \ldots , a_n\) in non-decreasing order. In addition to that, you are given several queries consisting of indices \(i\) and \(j\). For each query, determine the most frequent value among the integers \(a_i, ..., a_j\).

Input

The first input line contains two inters integer \(n\) and \(q\), respectively the amount of numbers and and queries.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\): the sequence of integers.

The next \(q\) lines describe the queries: each contains two integers \(i \, j\) describing the query range.

Output

\(q\) lines, each with one integer: the number of occurrences of the most frequent value within the given range.

Constraints

• \( 1 \leq n \leq 10^5 \)
• \( 1 \leq q \leq 10^5 \)
• \( -10^5 \leq a_i \leq 10^5 \)
• \( 1 \leq i \leq j \leq n\)

10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10

1
4
3

• Query 1 (2–3): The range is [-1, 1], the most frequent values are -1 or 1 which appears once.
• Query 2 (1-10): The range is [-1, -1, 1, 1, 1, 1, 3, 10, 10, 10], the most frequent value is 1 which appears 4 times.
• Query 3 (5-10): The range is [1, 3, 10, 10, 10], the most frequent value is 10 which appears 3 times.