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 LittleElephantAndArray {
	static int n;
	public static void main(String[] args) {
		FastScanner scan=new FastScanner();
		PrintWriter out=new PrintWriter(System.out);
		n=scan.nextInt();
		int q=scan.nextInt();
		int[] a=new int[n];
		for(int i=0;i<n;i++) a[i]=scan.nextInt();
		int[] res=new int[q];
		query[] queries=new query[q];
		for(int i=0;i<q;i++) queries[i]=new query(i,scan.nextInt()-1,scan.nextInt()-1);
		Arrays.sort(queries);//oops
		int[] f=new int[100001];
		int l=0,r=-1,cur=0;
		for(int i=0;i<q;i++) {
			query x=queries[i];
			int tl=x.l,tr=x.r;
			while(l<tl) {
				if(a[l]<=1e5) {
					if(f[a[l]]==a[l]) cur--;
					if(f[a[l]]-1==a[l]) cur++;
					f[a[l]]--;
				}
				l++;
			}
			while(l>tl) {
				l--;
				if(a[l]<=1e5) {
					if(f[a[l]]==a[l]) cur--;
					if(f[a[l]]+1==a[l]) cur++;
					f[a[l]]++;
				}
			}
			while(r<tr) {
				r++;
				if(a[r]<=1e5) {
					if(f[a[r]]==a[r]) cur--;
					if(f[a[r]]+1==a[r]) cur++;
					f[a[r]]++;
				}
			}
			while(r>tr) {
				if(a[r]<=1e5) {
					if(f[a[r]]==a[r]) cur--;
					if(f[a[r]]-1==a[r]) cur++;
					f[a[r]]--;
				}
				r--;
			}
			res[x.id]=cur;
		}

		for(int i:res) out.println(i);
		out.close();
	}
	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner() {
			try	{
				br = new BufferedReader(new InputStreamReader(System.in));
				st = new StringTokenizer(br.readLine());
			} catch (Exception e){e.printStackTrace();}
		}

		public String next() {
			if (st.hasMoreTokens())	return st.nextToken();
			try {st = new StringTokenizer(br.readLine());}
			catch (Exception e) {e.printStackTrace();}
			return st.nextToken();
		}

		public int nextInt() {return Integer.parseInt(next());}

		public long nextLong() {return Long.parseLong(next());}

		public double nextDouble() {return Double.parseDouble(next());}

		public String nextLine() {
			String line = "";
			if(st.hasMoreTokens()) line = st.nextToken();
			else try {return br.readLine();}catch(IOException e){e.printStackTrace();}
			while(st.hasMoreTokens()) line += " "+st.nextToken();
			return line;
		}
	}
	static class query implements Comparable<query> {
		int id,l,r,bucket;
		query(int id, int l, int r) {
			this.id=id;
			this.l=l;
			this.r=r;
			bucket=(int)(l/Math.sqrt(n));
		}
		@Override
		public int compareTo(query o) {
			if(bucket==o.bucket) return r-o.r;
			return bucket-o.bucket;
		}
	}
}