Given an array ~A~ of size ~N~, support the ~Q~ of the following queries:

Count the number of elements appearing exactly once in the range ~[l, r]~.

Constraints

~1 \le N, Q \le 2 \times 10^5~

~1 \le l \le r \le N~

~1 \le A_i \le N~

Input Specification

The first line contains ~2~ integers ~N~ and ~Q~.

The second line contains ~N~ integers ~A_1, A_2, \ldots, A_N~, the elements of ~A~.

The next ~Q~ lines each contain ~2~ integers ~l_i~ and ~r_i~, representing a query on the range ~[l_i, r_i]~.

Output Specification

For each query output one integer on its own line, the answer to that query.

Sample Input

7 5
1 2 3 2 4 3 1
2 5
1 7
4 7
3 6
1 1

Sample Output

2
1
4
2
1