Poklon

Time limit5sMemory limit512 MB

Summary

For each query interval, count distinct values that occur exactly twice within it. N and Q go up to 500,000.

Level: Hard8 of 10
Topics: Prefix sum, Hash map, Segment tree
Solved: No attempts yet

Problem

Little Mirko is a very simple man. His friend Darko has given him an array of $N$ positive integers and asked him $Q$ queries about the array, which Mirko must answer.

Each query consists of two integers: the positions of the left and right ends of an interval in the array. The answer to a query is the number of distinct values that appear exactly twice in the given interval.

Input

The first line contains the integers $N$ and $Q$ ( $1 \le N, Q \le 500\,000$ ).

The second line contains $N$ positive integers, the elements of the array. Each of them is less than $1\,000\,000\,000$ .

Each of the following $Q$ lines contains two integers $L$ and $R$ ( $1 \le L \le R \le N$ ) describing one query.

Output

Print $Q$ lines. Line $i$ contains the answer to the $i$ -th query, in the order the queries are given.

Hint

In the first example, the interval from the first to the third element contains only one number (the number 1) that appears exactly twice.

Examples3

Example 1
Input
```
5 1
1 2 1 1 1
1 3
```
Expected output
```
1
```
Example 2
Input
```
5 2
1 1 1 1 1
2 4
2 3
```
Expected output
```
0
1
```
Example 3
Input
```
5 2
1 1 2 2 3
1 1
1 5
```
Expected output
```
0
2
```