A8758 | Little Elephant and Array

The Little Elephant loves playing with arrays. He has array $a$ , consisting of $n$ positive integers, indexed from 1 to $n$ . Let's denote the number with index $i$ as $a_{i}$ .

Additionally the Little Elephant has $m$ queries to the array, each query is characterised by a pair of integers $l_{j}$ and $r_{j}$ $(1<=l_{j}<=r_{j}<=n)$ . For each query $l_{j},r_{j}$ the Little Elephant has to count, how many numbers $x$ exist, such that number $x$ occurs exactly $x$ times among numbers $a_{lj},a_{lj}+1,...,a_{rj}$ .

Help the Little Elephant to count the answers to all queries.

The first line contains two space-separated integers $n$ and $m$ $(1<=n,m<=10^{5})$ — the size of array $a$ and the number of queries to it. The next line contains $n$ space-separated positive integers $a_{1}$ , $a_{2}$ , $...$ , $a_{n}$ $(1<=a_{i}<=10^{9})$ . Next $m$ lines contain descriptions of queries, one per line. The $j$ -th of these lines contains the description of the $j$ -th query as two space-separated integers $l_{j}$ and $r_{j}$ $(1<=l_{j}<=r_{j}<=n)$ .

In $m$ lines print $m$ integers — the answers to the queries. The $j$ -th line should contain the answer to the $j$ -th query.