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.*;

import static java.lang.Math.*;

public class B {
	BufferedReader br;
	StringTokenizer st;
	PrintWriter out;

	void solve() throws IOException {
		int n = nextInt();
		int m = nextInt();

		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = min(nextInt() - 1, n);
		}
		int[] num = new int[n + 1];
		int[] prev = new int[n];
		Arrays.fill(num, -1);
		for (int i = 0; i < n; i++) {
			prev[i] = num[a[i]];
			num[a[i]] = i;
		}
		int[] count = new int[n];
		for (int i = 0; i < n; i++) {
			if (prev[i] == -1) {
				count[i] = 1;
			} else {
				count[i] = 1 + count[prev[i]];
			}
		}
		int[] next = new int[n];
		Arrays.fill(next, -1);
		for (int i = 0; i < n; i++) {
			if (prev[i] != -1) {
				next[prev[i]] = i;
			}
		}
		int[] prevk = new int[n];
		for (int i = 0; i < n; i++) {
			if (count[i] == 1 || a[i] == 0) {
				prevk[i] = i;
				continue;
			}
			if (count[i] == 2) {
				prevk[i] = prev[i];
				continue;
			}
			if (count[i] <= a[i] + 1) {
				prevk[i] = prevk[prev[i]];
				continue;
			}
			prevk[i] = next[prevk[prev[i]]];
		}
		int[] lind = new int[n];
		int[] sum = new int[n];
		int[] res = new int[m];
		ArrayList<Integer>[] l = new ArrayList[n];
		ArrayList<Integer>[] nm = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			l[i] = new ArrayList();
			nm[i] = new ArrayList();
		}
		for (int j = 0; j < m; j++) {
			int ll = nextInt() - 1;
			int r = nextInt() - 1;
			l[r].add(ll);
			nm[r].add(j);
		}
		int[] ind = new int[n + 1];
		int[] cnt = new int[n + 1];
		ArrayList<Integer> cur = new ArrayList();
		for (int i = 0; i < n; i++) {
			cnt[a[i]]++;
			ind[a[i]] = i;
			if (cnt[a[i]] == a[i] + 1) {
				cur.add(a[i]);
			}
			for (int j = 0; j < l[i].size(); j++) {
				int k = l[i].get(j);
				int pos = nm[i].get(j);
				for (int cand : cur) {
					if (ind[cand] >= k && prevk[ind[cand]] >= k
							&& prev[prevk[ind[cand]]] < k) {
						res[pos]++;
					}
				}
			}
		}
		for (int i = 0; i < m; i++) {
			out.println(res[i]);
		}

	}

	void run() {
		try {
			// br = new BufferedReader(new FileReader("G.in"));
			// out = new PrintWriter("G.out");

			br = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);

			solve();

			out.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	public static void main(String[] args) {
		new B().run();
	}

	public String nextToken() throws IOException {
		while ((st == null) || (!st.hasMoreTokens()))
			st = new StringTokenizer(br.readLine());
		return st.nextToken();
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	public long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}
}