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 LilElephantAndArray{

	static FastReader sc=new FastReader();
	
	private static int blockSize;
	
	private static int ans=0;
	
	private static Map<Integer, Integer> map=new HashMap<Integer, Integer>();

	static class Query{
		int L;
		int R;
		int pos;

		Query(int L,int R,int pos){
			this.L=L;
			this.R=R;
			this.pos=pos;
		}

		public String toString(){
			return " L : " + L +" R : "+ R+" pos : "+pos;
		}
	}

	static class SortComparator implements Comparator<Query>{

		@Override
		public int compare(Query o1,Query o2){
			if(o1.L/blockSize!=o2.L/blockSize){
				return o1.L/blockSize-o2.L/blockSize;
			}
			return o1.R-o2.R;
		}
	}

	public static void remove(int key){
		Integer count = map.get(key);
		if(count == null)
			count = 0;
		
		if(count-- == key)
			ans--;
		else if(count == key)
			ans++;
		
		map.put(key, count);
	}
	
	public static void add(int key) {
		Integer count = map.get(key);
		if(count == null)
			count = 0;
		
		if(count++ == key)
			ans--;
		else if(count == key)
			ans++;
		
		map.put(key, count);
	}
	
	

	public static void main(String args[]) throws IOException{

		int n=sc.nextInt();
		int m=sc.nextInt();

		blockSize=(int)(Math.sqrt(n));

		int a[]=new int[n];
		Query query[]=new Query[m];

		for(int i=0;i<n;i++){
			a[i]=sc.nextInt();
		}

		for(int i=0;i<m;i++){
			int l=sc.nextInt();
			int r=sc.nextInt();

			query[i]=new Query(l-1,r-1,i);
		}


		Arrays.sort(query,new SortComparator());

		/*for(int i=0;i<m;i++){
			System.out.println(query[i]);
		}*/

		int cl=0,cr=0;

		int res[]=new int[m];
		for(int i=0;i<m;i++){
			int l=query[i].L;int r=query[i].R;

			while(cl<l){
				remove(a[cl]);
				cl++;
			}
			while(cl>l) {
				add(a[cl-1]);
				cl--;
			}
			while(cr<=r) {
				add(a[cr]);
				cr++;
			}
			while(cr>r+1) {
				remove(a[cr-1]);
				cr--;
			}
			
			res[query[i].pos]=ans;
		}
		
		for(int i=0;i<res.length;i++) {
			System.out.println(res[i]);
		}

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