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 taskB {

	PrintWriter out;
	BufferedReader br;
	StringTokenizer st;

	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 long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

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

	class Query implements Comparable<Query> {
		int num, l, r;

		@Override
		public int compareTo(Query arg0) {
			return l - arg0.l;
		}

		public Query(int num, int l, int r) {
			super();
			this.num = num;
			this.l = l;
			this.r = r;
		}

	}

	int get(int[] a, int x) {
		x++;
		int ans = 0;
		while (x > 0) {
			ans += a[x];
			x = x & (x - 1);
		}
		return ans;
	}

	void add(int[] a, int d, int x) {
		if (d > a.length)
			return;
		if (d < 0)
			return;
		d++;
		while (d < a.length) {
			a[d] += x;
			d = d * 2 - (d & (d - 1));
		}
	}
	
	int sum(int[] f, int l, int r) {
		return -get(f, l - 1) + get(f, r);
	}

	public void solve() throws IOException {
		int n = nextInt();
		int m = nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		Query[] q = new Query[m];
		for (int i = 0; i < m; i++)
			q[i] = new Query(i, nextInt() - 1, nextInt() - 1);
		Arrays.sort(q);
		int[] last = new int[n + 1];
		Arrays.fill(last, Integer.MAX_VALUE);
		int[] next = new int[n];
		for (int i = n - 1; i >= 0; i--) {
			if (a[i] > n) {
				next[i] = -1;
				continue;
			} else {
				next[i] = last[a[i]];
				last[a[i]] = i;
			}
		}
		int[] fenv = new int[n + 1];
		TreeSet<Integer> was = new TreeSet<Integer>();
		int[] goodNext = new int[n];
		Arrays.fill(goodNext, Integer.MAX_VALUE);
		for (int i = 0; i < n; i++) {
			if ((a[i] > n) || (was.contains(a[i])))
				continue;
			was.add(a[i]);
			int t = i;
			for (int j = 0; (j < a[i] - 1) && (t < a.length); j++) {
				if (t < next.length)
					t = next[t];
			}
			add(fenv, t, 1);
			if (t < next.length)
				add(fenv, next[t], -1);
			goodNext[i] = t;
		}
		int curQ = 0;
		int[] ans = new int[m];
		for (int i = 0; i < n; i++) {
			while ((curQ < q.length) && (q[curQ].l == i)) {
				ans[q[curQ].num] = sum(fenv, i, q[curQ].r);
				curQ++;
			}
			if (goodNext[i] > a.length)
				continue;
			add(fenv, goodNext[i], -1);
			add(fenv, next[goodNext[i]], 2);
			if (next[goodNext[i]] < a.length)
				add(fenv, next[next[goodNext[i]]], -1);
			if (next[i] > a.length)
				continue;
			goodNext[next[i]] = next[goodNext[i]];
		}
		for (int x : ans)
			out.println(x);
	}

	public void run() {
		try {
			br = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);

			//br = new BufferedReader(new FileReader("taskB.in"));
			//out = new PrintWriter("taskB.out");

			solve();

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

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