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.util.*;import java.io.*;import java.math.*;
public class Main
{
    static int block;
    static class Node
    {
        int l,r,ind;
        Node(int l,int r,int ind)
        {
            this.l=l;
            this.r=r;
            this.ind=ind;
        }
    }
        public static class CustomSort implements Comparator<Node>{
        public int compare(Node a,Node b){
                if(a.l/block!=b.l/block)
                    return a.l-b.l;
                return (a.r-b.r);
        
        }
    }
    public static void process()throws IOException
    {
        int n=ni();
        int m=ni();
        block=(int)Math.sqrt(n);
        int[]freq=new int[n+1];
        int[]A=nai(n);
        Node[]q=new Node[m];
        int[]ans=new int[m];
        for(int i=0;i<m;i++)
            q[i]=new Node(ni()-1,ni()-1,i);
        Arrays.sort(q,new CustomSort());
        for(int i=0;i<m;i++)
            System.err.println(q[i].l+" "+q[i].r+" "+q[i].ind);
        int currL=0,currR=0;
        int c=0;
        for(int i=0;i<m;i++)
        {
            int L=q[i].l;
            int R=q[i].r;
            while(currL<L)
            {
                if(A[currL]<=n)
                {
                    if(freq[A[currL]]==A[currL])
                        c--;
                    freq[A[currL]]--;
                    if(freq[A[currL]]==A[currL])
                        c++;
                }
                currL++;
            }
            while(currL>L)
            {
                currL--;
                if(A[currL]<=n)
                {
                    if(freq[A[currL]]==A[currL])
                        c--;
                    freq[A[currL]]++;
                    if(freq[A[currL]]==A[currL])
                        c++;
                }
            }
            while(currR<=R)
            {
                if(A[currR]<=n)
                {
                    if(freq[A[currR]]==A[currR])
                        c--;
                    freq[A[currR]]++;
                    if(freq[A[currR]]==A[currR])
                        c++;
                }
                currR++;
            }
            while(currR>R+1)
            {
                if(A[currR-1]<=n)
                {
                    if(freq[A[currR-1]]==A[currR-1])
                        c--;
                    freq[A[currR-1]]--;
                    if(freq[A[currR-1]]==A[currR-1])
                        c++;
                }
                currR--;
            }
            ans[q[i].ind]=c;
        }
        for(int i=0;i<m;i++)
            pn(ans[i]);
    }

    static long mod=(long)1e8;
    static AnotherReader sc;
    static PrintWriter out;
    public static void main(String[]args)throws IOException
    {
        boolean oj = true;
        if(oj){sc=new AnotherReader();out=new PrintWriter(System.out);}
        else{sc=new AnotherReader(100);out=new PrintWriter("output.txt");}
        int t=1;
        // t=ni();
        while(t-->0) {process();}
        out.flush();out.close();  
    }

    static void pn(Object o){out.println(o);}
    static void p(Object o){out.print(o);}
    static void pni(Object o){out.println(o);out.flush();}
    static int ni()throws IOException{return sc.nextInt();}
    static long nl()throws IOException{return sc.nextLong();}
    static double nd()throws IOException{return sc.nextDouble();}
    static String nln()throws IOException{return sc.nextLine();}
    static int[] nai(int N)throws IOException{int[]A=new int[N];for(int i=0;i!=N;i++){A[i]=ni();}return A;}
    static long[] nal(int N)throws IOException{long[]A=new long[N];for(int i=0;i!=N;i++){A[i]=nl();}return A;}
    static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}

/////////////////////////////////////////////////////////////////////////////////////////////////////////

    static class AnotherReader{BufferedReader br; StringTokenizer st;
    AnotherReader()throws FileNotFoundException{
    br=new BufferedReader(new InputStreamReader(System.in));}
    AnotherReader(int a)throws FileNotFoundException{
    br = new BufferedReader(new FileReader("input.txt"));}
    String next()throws IOException{
    while (st == null || !st.hasMoreElements()) {try{
    st = new StringTokenizer(br.readLine());}
    catch (IOException  e){ e.printStackTrace(); }}
    return st.nextToken(); } int nextInt() throws IOException{
    return Integer.parseInt(next());}
    long nextLong() throws IOException
    {return Long.parseLong(next());}
    double nextDouble()throws IOException { return Double.parseDouble(next()); }
    String nextLine() throws IOException{ String str = ""; try{
    str = br.readLine();} catch (IOException e){
    e.printStackTrace();} return str;}}
   
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}



