Description

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]$.

Input Format

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 Format

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

5 1
1 2 1 1 1
1 3

1

5 2
1 1 1 1 1
2 4
2 3

0
1

5 2
1 1 2 2 3
1 1
1 5

0
2

Hint

[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 CONTEST #5 T5 Poklon.

The score of this problem follows the original COCI setting, with a full score of $140$.

Translated by ChatGPT 5