Little Mirko is a very simple man. Mirko's friend Darko has given him an array of ~N~ natural integers and asked him ~Q~ queries about the array that Mirko must answer. Each query consists of two integers, the positions of the left and right end of an interval in the array. The answer to the query is the number of different values that appear exactly twice in the given interval.

Input Specification

The first line of input contains the integers ~N~ and ~Q~ ~(1 \leq N, Q \leq 500\,000)~.

The second line of input contains ~N~ natural integers less than ~1\,000\,000\,000~, the elements of the array.

Each of the following ~Q~ lines contains two integers, ~L~ and ~R~ ~(1 \leq L \leq R \leq N)~, from the task.

Output Specification

The output must consist of ~Q~ lines, each line containing the answer to a query, respectively.

Scoring

In test cases worth ~56~ points in total, the numbers ~N~ and ~Q~ will not be larger than ~5000~.

Sample Input 1

5 1
1 2 1 1 1
1 3

Sample Output 1

1

Explanation for Sample Output 1

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

Sample Input 2

5 2
1 1 1 1 1
2 4
2 3

Sample Output 2

0
1

Sample Input 3

5 2
1 1 2 2 3
1 1
1 5

Sample Output 3

0
2