Description

There are $n$ problems in this contest, each with a difficulty value $a_i$. Since the ace coder wangxz has already sorted these difficulty values in ascending order for Niaoge, he does not want to know which problems are easy or hard; he only wants to know, among some problems $a_l,a_{l+1},\ldots,a_r$, how many times the most frequent difficulty value appears.

Your task is: for each query $(l, r)$, tell him, among the $(r-l+1)$ problems from $a_l$ to $a_r$, the number of occurrences of the most frequent difficulty value (there are $q$ queries in total).

If you succeed in helping Niaoge, he will take you through the NOI Qualifier.

Input Format

Each test point contains exactly one set of testdata.

The first line contains two integers, the number of problems $n$ and the number of queries $q$.

The second line has $n$ integers; the $i$-th integer $a_i$ is the difficulty of the $i$-th problem.

Then follow $q$ lines, each with two integers $l, r$, representing one query.

Output Format

For each query, output a single integer on its own line as the answer.

9 1
1 1 1 2 2 3 3 4 4
3 8

2

Hint

Constraints

对于全部的测试点，保证 $1 \leq n \leq 10^5$，$1 \leq q \leq 2\times 10^5$，$-10^5 \leq a_i \leq 10^5$，$1 \leq l \leq r \leq n$。

Translated by ChatGPT 5