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.*;
import java.math.*;

public class Main {

	public static BufferedReader in = new BufferedReader(new InputStreamReader(
			System.in));
	static StringTokenizer st = null;

	static String nx() throws Exception {
		for (; st == null || !st.hasMoreTokens();) {
			String k1 = in.readLine();
			if (k1 == null)
				return null;
			st = new StringTokenizer(k1);
		}
		return st.nextToken();
	}

	static int ni() throws Exception {
		return Integer.parseInt(nx());
	}

	public static void main(String[] args) throws Exception {
		int n1 = ni();
		int m1 = ni();
		int[] l1 = new int[n1];
		int[] count = new int[n1 + 1];
		for (int i =0; i < n1; i++){
			l1[i] = ni();
			if (l1[i] <= n1){
				count[l1[i]]++;
			}
		}
		// px(l1);
		int goodno = 0;
		int[] good = new int[n1 + 1];
		int[] id = new int[n1 + 1];
		Arrays.fill(id, -1);
		for (int i = 1; i <= n1; i++) {
			if (count[i] >= i) {
				id[i] = goodno;
				good[goodno++] = i;

			}
		}
		// px(Arrays.copyOf(good, goodno));
		int[] exCount = new int[goodno * (n1 + 1)];
		for (int i = 0; i < n1; i++) {
			if (l1[i] <= n1 && count[l1[i]] >= l1[i])
				exCount[(i + 1) * goodno + id[l1[i]]]++;
		}
		for (int i = 1; i <= n1; i++){
			for (int j = 0; j< goodno; j++){
				exCount[i * goodno + j] += exCount[(i - 1) * goodno + j];
			}
		}
		for (int i = 0; i < m1; i++) {
			int left = ni() - 1;
			int right = ni();
			int ans = 0;
			for (int j = 0; j < goodno; j++) {
				// int have = exCount[j * n1 + right]
				// - (left == 0 ? 0 : exCount[j * n1 + left - 1]);
				// px(have, exCount[j][left], right == 0);
				if (exCount[right * goodno + j] - exCount[left * goodno + j] == good[j])
					ans++;
			}
			out.println(ans);
		}

		out.flush();
	}

	static PrintWriter out = new PrintWriter(System.out);

	static void px(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}