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.*;
import java.util.*;
public class Solution
{
    
    public static void main (String[] args) throws java.lang.Exception
    {
        Scan sn=new Scan();
        Print p=new Print();
        int n=sn.scanInt();
        int m=sn.scanInt();
        int[]arr=new int[n];
        for(int i=0;i<n;i++)
        arr[i]=sn.scanInt();
        Pair[]query=new Pair[m];
        for(int i=0;i<m;i++)
        query[i]=new Pair((sn.scanInt()-1),(sn.scanInt()-1),n,i);
        Arrays.sort(query);
        /*for(int i=0;i<m;i++)
        System.out.println(query[i].l+" "+query[i].r);*/
        int[]count=new int[100001];
        int currl=0,currr=0;int []ans=new int[m];int ans1=0;
        for(int i=0;i<m;i++)
        {
            while(currl<query[i].l)
            {
                if(arr[currl]<100001){
                count[arr[currl]]--;
                if(count[arr[currl]]==arr[currl])
                ans1++;
                if(count[arr[currl]]+1==arr[currl])
                ans1--;}
                currl++;
            }
            while(currl>query[i].l)
            {
                if(arr[currl-1]<100001){
                count[arr[currl-1]]++;
                if(count[arr[currl-1]]==arr[currl-1])
                ans1++;
                if(count[arr[currl-1]]-1==arr[currl-1])
                ans1--;}
                currl--;
            }
            while(currr<=(query[i].r))
            {
                if(arr[currr]<100001){
                count[arr[currr]]++;
                if(count[arr[currr]]==arr[currr])
                ans1++;
                if(count[arr[currr]]-1==arr[currr])
                ans1--;}
                currr++;
            }
            //System.out.println(currr+" "+currl);
            while(currr>(query[i].r+1))
            {
                if(arr[currr-1]<100001){
                count[arr[currr-1]]--;
                if(count[arr[currr-1]]==arr[currr-1])
                ans1++;
                if(count[arr[currr-1]]+1==arr[currr-1])
                ans1--;}
                currr--;
            }
            ans[query[i].in]=ans1;
            
        }
        for(int a: ans)
        p.printLine(Integer.toString(a));
        p.close();
    }
}
class Pair implements Comparable<Pair> {
		int l;
		int r;
		int n;
		int in;
		Pair(int a, int b,int c,int d){
			l=a;
	        r=b;
	        n=(int)Math.sqrt(c);
	        in=d;
		}
		@Override
		public int compareTo(Pair o) {
			if((l/n)!=(o.l/n))
			return Integer.compare((Integer)l,(Integer)o.l);
			else
			return Integer.compare((Integer)r,(Integer)o.r);
		}}
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;
    }
}

class Print
{
    private final BufferedWriter bw;
    public Print()
    {
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
    }
    public void print(String str)throws IOException
    {
        bw.append(str);
    }
    public void printLine(String str)throws IOException
    {
        print(str);
        bw.append("\n");
    }
    public void close()throws IOException
    {
        bw.close();
    }}