Background

Update on July 29, 2024: Added a set of hack testdata; previously, all testdata satisfied $q\le 10^5$.

Since crushing NOIP2013, Niaoge (faebdc) has kept studying hard, solving problems on various OJs every day, and contests are usually a breeze for him. But today he ran into a small problem: at an "Orz Niaoge Cup", there were just too many problems! Niaoge felt dizzy and needs your help.

Problem 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