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
// practice with kaiboy
import java.io.*;
import java.util.*;

public class CF221D extends PrintWriter {
	CF221D() { super(System.out); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF221D o = new CF221D(); o.main(); o.flush();
	}

	int[] ft;
	void update(int i, int n, int a) {
		while (i < n) {
			ft[i] += a;
			i |= i + 1;
		}
	}
	int query(int i) {
		int a = 0;
		while (i >= 0) {
			a += ft[i];
			i &= i + 1; i--;
		}
		return a;
	}
	void main() {
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] aa = new int[n];
		for (int i = 0; i < n; i++) {
			int a = sc.nextInt();
			if (a > n)
				a = 0;
			aa[i] = a;
		}
		int[] ia = new int[n + 1]; Arrays.fill(ia, -1);
		int[] ka = new int[n + 1];
		int[] pp = new int[n];
		int[] kk = new int[n];
		for (int i = 0; i < n; i++) {
			int a = aa[i];
			if (a > 0) {
				pp[i] = ia[a]; ia[a] = i;
				kk[i] = ka[a]++;
			}
		}
		int[] ll = new int[m];
		int[] rr = new int[m];
		int[] ans = new int[m];
		Integer[] hh = new Integer[m];
		for (int h = 0; h < m; h++) {
			ll[h] = sc.nextInt() - 1;
			rr[h] = sc.nextInt() - 1;
			hh[h] = h;
		}
		Arrays.sort(hh, (h1, h2) -> ll[h2] - ll[h1]);
		ft = new int[n];
		for (int h = 0, h_, i = n - 1, j; i >= 0; i--) {
			int a = aa[i];
			if (a > 0 && (j = ia[a]) >= i) {
				int k = kk[j] - kk[i];
				if (k == a - 1) {
					// 0
					// 1
					update(j, n, 1);
				} else if (k == a) {
					// 0 1
					// 1 -1
					update(j, n, -2);
					update(pp[j], n, 1);
				} else if (k == a + 1) {
					// 0 1 -1
					// 1 -1 0
					update(j, n, 1);
					ia[a] = j = pp[j];
					update(j, n, -2);
					update(pp[j], n, 1);
				}
			}
			while (h < m && ll[h_ = hh[h]] == i) {
				ans[h_] = query(rr[h_]);
				h++;
			}
		}
		for (int h = 0; h < m; h++)
			println(ans[h]);
	}
}
