P7764 [COCI 2016/2017 #5] Poklon

You are given an array containing $N$ natural numbers. Then you need to answer $Q$ queries. For each query, output the number of natural numbers that appear exactly twice in the interval $[L, R]$.

The first line contains two integers $N, Q$, representing the number of elements in the array and the number of queries. The second line contains $N$ integers, representing the elements in the array. The next $Q$ lines each contain two integers $L, R$, representing the query interval.

Output $Q$ lines. Each line corresponds to the answer for one query.

**[Sample 1 Explanation]** In the interval $[1, 3]$, only $1$ appears exactly twice. **[Constraints]** For $40\%$ of the testdata, $N, Q \le 5000$. For $100\%$ of the testdata, $1 \le N, Q \le 5 \times 10^5$, $1 \le L \le R \le N$, and all elements in the array are natural numbers less than $10^9$. **[Hints and Notes]** **This problem is translated from [COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #5](https://hsin.hr/coci/archive/2016_2017/contest5_tasks.pdf) _T5 Poklon_.** **The score of this problem follows the original COCI setting, with a full score of $140$.** Translated by ChatGPT 5