Minho's Wish

Minho has a sequence $A_1, A_2, \dots, A_N$ of length $N$. He names two integers $x$ and $y$, then asks how many different numbers appear at least three times in the range $[x, y]$.

Report the number of distinct values, not the total number of occurrences. For example, if the numbers in the range are $1, 3, 3, 3, 3, 2, 2, 2, 7, 1, 7$, then $3$ appears four times and $2$ appears three times, so the answer is $2$.

Answer all $Q$ of Minho's wishes.

The first line contains $N$ and $Q$ separated by a space ($1 \le N, Q \le 100\,000$), the length of Minho's sequence and the number of wishes he will name.

The second line contains the elements $A_i$ in order, separated by spaces ($1 \le A_i \le 100\,000$, $1 \le i \le N$).

Each of the next $Q$ lines contains $x$ and $y$ for one wish, separated by a space ($1 \le x \le y \le N$).

Print the answer to each wish on its own line, in the order the wishes are given.