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.*;
public class Main {
    static class Scan {
        private byte[] buf=new byte[1024];
        private int index;
        private InputStream in;
        private int total;
        public Scan()
        {
            in=System.in;
        }
        public int scan()throws IOException
        {
            if(total<0)
            throw new InputMismatchException();
            if(index>=total)
            {
                index=0;
                total=in.read(buf);
                if(total<=0)
                return -1;
            }
            return buf[index++];
        }
        public int scanInt()throws IOException
        {
            int integer=0;
            int n=scan();
            while(isWhiteSpace(n))
            n=scan();
            int neg=1;
            if(n=='-')
            {
                neg=-1;
                n=scan();
            }
            while(!isWhiteSpace(n))
            {
                if(n>='0'&&n<='9')
                {
                    integer*=10;
                    integer+=n-'0';
                    n=scan();
                }
                else throw new InputMismatchException();
            }
            return neg*integer;
        }
        public double scanDouble()throws IOException
        {
            double doub=0;
            int n=scan();
            while(isWhiteSpace(n))
            n=scan();
            int neg=1;
            if(n=='-')
            {
                neg=-1;
                n=scan();
            }
            while(!isWhiteSpace(n)&&n!='.')
            {
                if(n>='0'&&n<='9')
                {
                    doub*=10;
                    doub+=n-'0';
                    n=scan();
                }
                else throw new InputMismatchException();
            }
            if(n=='.')
            {
                n=scan();
                double temp=1;
                while(!isWhiteSpace(n))
                {
                    if(n>='0'&&n<='9')
                    {
                        temp/=10;
                        doub+=(n-'0')*temp;
                        n=scan();
                    }
                    else throw new InputMismatchException();
                }
            }
            return doub*neg;
        }
        public String scanString()throws IOException
        {
            StringBuilder sb=new StringBuilder();
            int n=scan();
            while(isWhiteSpace(n))
            n=scan();
            while(!isWhiteSpace(n))
            {
                sb.append((char)n);
                n=scan();
            }
            return sb.toString();
        }
        private boolean isWhiteSpace(int n)
        {
            if(n==' '||n=='\n'||n=='\r'||n=='\t'||n==-1)
            return true;
            return false;
        }
    }
    public static void main(String args[]) throws IOException {
        Scan input=new Scan();
        int n=input.scanInt();
        int m=input.scanInt();
        int arr[]=new int[n];
        int cpy[]=new int[n];
        for(int i=0;i<n;i++) {
            arr[i]=input.scanInt();
            cpy[i]=arr[i];
        }
        ArrayList<Integer> arrli=new ArrayList<>();
        Arrays.sort(cpy);
        for(int i=0;i<n;i++) {
            int j=i,cnt=0;
            while(j<n && cpy[j]==cpy[i]) {
                j++;
                cnt++;
            }
            if(cnt>=cpy[i]) {
                arrli.add(cpy[i]);
            }
            i=j-1;
        }
        int freq[][]=new int[arrli.size()][n];
        for(int i=0;i<arrli.size();i++) {
            int cnt=0;
            for(int j=0;j<n;j++) {
                if(arr[j]==arrli.get(i)) {
                    cnt++;
                }
                freq[i][j]=cnt;
            }
        }
//        for(int i=0;i<freq.length;i++) {
//            for(int j=0;j<n;j++) {
//                System.out.print(freq[i][j]+" ");
//            }
//            System.out.println();
//        }
//        System.out.println(arrli.size());
        StringBuilder ans=new StringBuilder("");
        for(int i=0;i<m;i++) {
            int l=input.scanInt()-1;
            int r=input.scanInt()-1;
            int cnt=0;
            for(int j=0;j<freq.length;j++) {
                if((freq[j][r]-(l>0?freq[j][l-1]:0))==arrli.get(j)) {
                    cnt++;
                }
            }
            ans.append(cnt+"\n");
        }
        System.out.println(ans);
    }
}
