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 B implements Runnable{
	public static void main (String[] args) {new Thread(null, new B(), "_cf", 1 << 28).start();}

	int n, size, max;

	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);

		n = fs.nextInt();
		int m = fs.nextInt();
		
		size = (int)Math.sqrt(n);
		
		int[] a = fs.nextIntArray(n);
		Query[] q = new Query[m];
		for(int i = 0; i < m; i++)
			q[i] = new Query(fs.nextInt()-1, fs.nextInt()-1, i);

//		brute(a, q);
		
		int[] need = new int[n];
		HashMap<Integer, Integer> map = new HashMap<>();
		for(int i = 0; i < n; i++) {
			if(!map.containsKey(a[i])) {
				map.put(a[i], map.size());
			}
			need[map.get(a[i])] = a[i];
		}
		
		for(int i = 0; i < n; i++) {
			a[i] = map.get(a[i]);
		}
		
//		System.out.println(map);
//		System.out.println(Arrays.toString(need));
		
		
		Arrays.sort(q);
		
		int left = 0, right = -1;
		int ans = 0;
		int[] res = new int[m];
		int[] freq = new int[n + 1];
//		HashMap<Integer, Integer> freq = new HashMap<>();
		
		for(Query qq : q) {
//			System.out.println(Arrays.toString(freq) + " " + left + " " + right);
			while(right < qq.r) {
				right++;
				if(freq[a[right]] == need[a[right]]) ans--;
				freq[a[right]]++;
				if(freq[a[right]] == need[a[right]]) ans++;
			}
			while(right > qq.r) {
				if(freq[a[right]] == need[a[right]]) ans--;
				freq[a[right]]--;
				if(freq[a[right]] == need[a[right]]) ans++;
				right--;
			}
			while(left < qq.l) {
				if(freq[a[left]] == need[a[left]]) ans--;
				freq[a[left]]--;
				if(freq[a[left]] == need[a[left]]) ans++;
				left++;
			}
			while(left > qq.l) {
				left--;
				if(freq[a[left]] == need[a[left]]) ans--;
				freq[a[left]]++;
				if(freq[a[left]] == need[a[left]]) ans++;
			}
			res[qq.id] = ans;
		}
		
		for(Integer i : res) out.println(i);
		
		out.close();
	}
	
	void brute (int[] a, Query[] q) {
		for(int i = 0; i < q.length; i++) {
			int[] freq = new int[100];
			int res = 0;
//			System.out.println(q[i].l + " " + q[i].r + " " + q[i].id);
			for(int j = q[i].l; j <= q[i].r; j++) {
				freq[a[j]]++;
			}
			for(int j = 1; j < freq.length; j++) {
				if(freq[j] == j) {
					res++;
				}
			}
			System.out.println(res);
		}
		System.out.println();
	}
	
	class Query implements Comparable<Query> {
		int l, r, id;
		Query (int a, int b, int c) {
			l = a;
			r = b;
			id = c;
		}
		public int compareTo(Query o) {
			if(l / size == o.l / size) return Integer.compare(r, o.r);
			return Integer.compare(l / size, o.l / size);
		}
	}

	void sort (int[] a) {
		int n = a.length;
		for(int i = 0; i < 1000; i++) {
			Random r = new Random();
			int x = r.nextInt(n), y = r.nextInt(n);
			int temp = a[x];
			a[x] = a[y];
			a[y] = temp;
		}
		Arrays.sort(a);
	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;
		public FastScanner() {
			try	{
				br = new BufferedReader(new InputStreamReader(System.in));
//				br = new BufferedReader(new FileReader("cases.in"));
				st = new StringTokenizer("");
			} 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 = "";
			try {line = br.readLine();}
			catch (Exception e) {e.printStackTrace();}
			return line;
		}
		public Integer[] nextIntegerArray(int n) {
			Integer[] a = new Integer[n];
			for(int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for(int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
		public char[] nextCharArray() {return nextLine().toCharArray();}
	}

}  