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.util.*;
public class Solution {
	static class FastReader {
        BufferedReader br; 
        StringTokenizer st; 
        public FastReader() {
        	boolean env=System.getProperty("ONLINE_JUDGE") != null;
        	if(!env) {
        		try {
					br=new BufferedReader(new FileReader("src\\input.txt"));
				} catch (FileNotFoundException e) {
					e.printStackTrace();
				}
        	}
        	else 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; 
        } 
    }
	static FastReader sc=new FastReader();
	static PrintWriter out=new PrintWriter(System.out);
	//debug
	static void debug(Object... o) {
        System.out.println(Arrays.deepToString(o));
    }
	//Main
	static class query{
		int l,r,id;
		query(int a,int b,int c){
			l=a;
			r=b;
			id=c;
		}
	}
	static Comparator<query> cmp=new Comparator<query>() {
		public int compare(query q1, query q2) {
			if(q1.l/BLOCK==q2.l/BLOCK) return q1.r-q2.r;
			return q1.l/BLOCK-q2.l/BLOCK;
		}
	};
	static int n,a[],BLOCK=400,cur=0;
	static int map[]=new int[100000+1];
	static void add(int idx) {
		if(a[idx]>100000) return;
		if(map[a[idx]]==a[idx]) cur--;
		map[a[idx]]++;
		if(map[a[idx]]==a[idx]) cur++;
	}
	static void remove(int idx) {
		if(a[idx]>100000) return;
		if(map[a[idx]]==a[idx]) cur--;
		map[a[idx]]--;
		if(map[a[idx]]==a[idx]) cur++;
	}
	public static void main(String args[]) {
		int test=1;
		//test=sc.nextInt();
		while(test-->0) {
			//Think before code, it won't hurt
			n=sc.nextInt();a=new int[n];
			int q=sc.nextInt();
			for(int i=0;i<n;i++) a[i]=sc.nextInt();
			query queries[]=new query[q];
			for(int i=0;i<q;i++) queries[i]=new query(sc.nextInt()-1,sc.nextInt()-1,i);
			Arrays.parallelSort(queries,cmp);
			int ans[]=new int[q],L=0,R=-1;
			for(query Q: queries) {
				//Expand
				while(Q.l<L) add(--L);
				while(Q.r>R) add(++R);
				//Shrink
				while(Q.l>L) remove(L++);
				while(Q.r<R) remove(R--);
				ans[Q.id]=cur;
			}
			for(int x: ans) out.println(x);
		}
		out.flush();
		out.close();
	}
}
