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*_{*l*_{*j*}}, *a*_{*l*_{*j*} + 1}, ..., *a*_{*r*_{*j*}}$.

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

Input

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*)$.

Output

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