Colorful Village 2

Minho looks after a country called Cheonnara, where there are $N$ houses. He numbered the houses 1 through $N$.

One day Minho painted every house in the country. Each paint has its own brightness, and a careless order would spoil the look of the village, so he painted the houses so that the paint never gets darker as the house number grows. In other words, the brightness of house $i$ is at most the brightness of house $i+1$.

Once the painting was done, Minho wanted to know how many times the most common brightness appears among the houses in a given range. Write a program that reports that count for every range he asks about.

The first line contains the number of houses $N$ and the number of ranges $Q$, separated by a space. ($1 \le N \le 100000$, $1 \le Q \le 100000$)

The second line contains the brightness values $P_1, P_2, \dots, P_N$ painted on houses 1 through $N$, in order. ($-100000 \le P_i \le 100000$, and $P_i \le P_{i+1}$ for every $i$.)

Each of the next $Q$ lines contains one range as two integers $X$ and $Y$ ($1 \le X \le Y \le N$), meaning the houses from $X$ to $Y$.

Print $Q$ lines. On the $i$-th line print how many times the most common brightness appears in the $i$-th range.