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,\dots ,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