Time limit:
5000 ms
Memory limit:
512 MB

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

The first line of input contains the integers N and Q (1 ≤ N, Q 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 ≤ L R N), from the task.

Output

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

Constrains/Subtasks

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

Editor:

Source: Croatian Open Competition in Informatics 2016/2017, contest 5 (COCI 2016 #5)

Select description language

English (raw)

If you don't find what you want

Translate it!

Edit this description

Edit

Tag

None