Problem Description

Given an array containing $N$ natural numbers.

You need to answer $Q$ queries, each asking for the number of natural numbers that appear exactly twice in the interval $[L, R]$.

Input Format

The first line contains two integers $N$ and $Q$, representing the number of elements in the array and the number of queries, respectively.

The second line contains $N$ integers, representing the elements of the array.

The next $Q$ lines each contain two integers $L$ and $R$, representing the queried interval.

Output Format

Output $Q$ lines, each corresponding to the result of each query.

Sample Input and Output

Input Sample #1

5 1
1 2 1 1 1
1 3

Output Sample #1

1

Input Sample #2

5 2
1 1 1 1 1
2 4
2 3

Output Sample #2

0
1

Input Sample #3

5 2
1 1 2 2 3
1 1
1 5

Output Sample #3

0
2

Notes

[Sample 1 Explanation]

In the interval $[1, 3]$, only the number $1$ appears exactly twice.

[Data Range and Constraints]

For $40\%$ of the data, $N, Q \le 5000$.

For $100\%$ of the data, $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$.

[Translation and Original Source]

This problem is translated from COCI 2016-2017 CONTEST #5 T5 Poklon.

This problem is scored according to the original COCI settings, with a maximum score of $140$.

见题面 Input 部分

见题面 Output 部分