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 java.io.*;
import java.math.BigInteger;
import static java.math.BigInteger.*;


import java.util.*;

public class Solution{


    void solve()throws Exception
    {

        int n=nextInt();
        int m=nextInt();
        int[]a=new int[n];
        for(int i=0;i<n;i++)
            a[i]=nextInt();
        HashMap<Integer,Integer>map=new HashMap<Integer, Integer>();
        for(int i=0;i<n;i++)
            if(map.containsKey(a[i]))
                map.put(a[i],map.get(a[i])+1);
            else
                map.put(a[i],1);
        ArrayList<Integer>important=new ArrayList<Integer>();
        for(Map.Entry<Integer,Integer>x : map.entrySet())
        {
            if(x.getValue()>=x.getKey())
            {
                important.add(x.getKey());
            }
        }
        int[]l=new int[m];
        int[]r=new int[m];
        int[]res=new int[m];
        for(int i=0;i<m;i++)
        {
            l[i]=nextInt()-1;
            r[i]=nextInt()-1;
        }
        for(int x: important)
        {
            int[]cnt=new int[n];
            for(int i=0;i<n;i++)
            {
                if(i!=0)
                    cnt[i]=cnt[i-1];
                if(x==a[i])
                    cnt[i]++;
            }
            for(int i=0;i<m;i++)
            {
                int num=cnt[r[i]];
                if(l[i]!=0)
                    num-=cnt[l[i]-1];
                if(num==x)
                    res[i]++;
            }

        }
        for(int i=0;i<m;i++)
            writer.println(res[i]);





    }





    ////////////
    BufferedReader reader;
    PrintWriter writer;
    StringTokenizer stk;
    void run()throws Exception
    {

        reader=new BufferedReader(new InputStreamReader(System.in));
        // reader=new BufferedReader(new FileReader("input.txt"));
        stk=null;
        writer=new PrintWriter(new PrintWriter(System.out));
        //writer=new PrintWriter(new FileWriter("output.txt"));
        solve();
        reader.close();
        writer.close();
    }
    int nextInt()throws Exception
    {
        return Integer.parseInt(nextToken());
    }

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

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


    }

    String nextString()throws Exception
    {
        return nextToken();
    }
    String nextLine()throws Exception
    {
        return reader.readLine();
    }
    String nextToken()throws Exception
    {
        if(stk==null || !stk.hasMoreTokens())
        {
            stk=new StringTokenizer(nextLine());
            return nextToken();

        }
        return stk.nextToken();
    }

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








}