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 ai. 

Additionally the Little Elephant has m queries to the array, each query is characterised by a pair of integers lj and rj (1 ≤ lj ≤ rj ≤ n). For each query lj, rj the Little Elephant has to count, how many numbers x exist, such that number x occurs exactly x times among numbers alj, alj + 1, ..., arj.

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 ≤ 105) — the size of array a and the number of queries to it. The next line contains n space-separated positive integers a1, a2, ..., an (1 ≤ ai ≤ 109). 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 lj and rj (1 ≤ lj ≤ rj ≤ 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.

Examples

Input

7 2
3 1 2 2 3 3 7
1 7
3 4


Output

3
1
import static java.util.Arrays.* ;
import static java.lang.Math.*  ;
import java.io.*;
import java.util.*;

public class Main
{
    int s ;
    int ans ;
    int [] count ;

    void add(int val)
    {
        if(val >= count.length) return;
        count[val]++ ;
        if(count[val] == val)
            ans ++ ;
        if(count[val] - 1 == val)
            ans -- ;
    }
    void remove(int val)
    {
        if(val >= count.length) return;
        count[val]-- ;
        if(count[val] == val)
            ans ++ ;
        if(count[val] + 1 == val)
            ans -- ;
    }
    void main() throws Exception
    {
        Scanner sc = new Scanner(System.in) ;
        PrintWriter out = new PrintWriter(System.out);
        int n = sc.nextInt() , m = sc.nextInt() ;
        int [] a = new int [n] ;
        count = new int [n + 1];
        for(int i = 0 ;i  < n ;i ++)
            a[i] = sc.nextInt();
        s = (int)ceil(sqrt(m + 1)) ;
        int L = 0 , R = -1 ;
        Query [] queries = new Query [m] ;
        for(int i = 0 ; i < m ; i ++)
            queries[i] = new Query(sc.nextInt() - 1, sc.nextInt() - 1 , i) ;
        int [] solution = new int [m] ;
        sort(queries);
        for(Query q : queries)
        {
            while (R < q.r) add(a[++R]);
            while (q.r < R) remove(a[R--]);
            while (q.l < L) add(a[--L]);
            while (q.l > L) remove(a[L++]);
            solution[q.idx] = ans ;
        }
        for(int x : solution)
            out.println(x);
        out.flush();
    }

    public static void main(String[] args) throws Exception { new Main().main(); }

    class Query implements Comparable<Query>
    {
        int l , r, idx , block;

        Query(int a , int b , int c)
        {
            l = a ; r = b ; idx = c ;
            block = l / s ;
        }

        @Override
        public int compareTo(Query o)
        {
            if(block != o.block)
                return block - o.block ;
            return r - o.r ;
        }
    }
    class Scanner
    {
        BufferedReader br ;
        StringTokenizer st ;

        Scanner(InputStream in)
        {
            br = new BufferedReader(new InputStreamReader(in)) ;
        }
        String next() throws Exception
        {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken() ;
        }
        int nextInt() throws Exception { return Integer.parseInt(next()) ; }

        long nextLong() throws Exception {return Long.parseLong(next());}

        double nextDouble() throws Exception {return Double.parseDouble(next());}

    }
}