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.awt.geom.Point2D;
import java.text.*;
import java.math.*;
import java.util.*;

public class Main implements Runnable {

	final String filename = "";

	public void solve() throws Exception {
		int n = iread(), m = iread();
		Number[] a = new Number[n];
		for (int i = 0; i < n; i++) {
			a[i] = new Number(iread(), i);
		}
		Number[] b = new Number[n];
		for (int i = 0; i < n; i++) {
			b[i] = a[i];
		}
		Arrays.sort(b);

		int[] cur = new int[n + 1];
		Arrays.fill(cur, n);

		int cnt = 1;
		b[n - 1].next = n;
		if (b[0].x==1)
			cur[1] = b[0].pos;
		for (int i = 0; i + 1 < n; i++) {
			if (b[i].x == b[i + 1].x) {
				b[i].next = b[i + 1].pos;
				cnt++;
				if (cnt == b[i].x)
					cur[b[i].x] = b[i + 1].pos;
			} else {
				b[i].next = n;
				cnt = 1;
			}
		}
		base = 1;
		while (base <= n)
			base *= 2;
		tree = new int[2 * base];
		Segment[] s = new Segment[m], s2 = new Segment[m];
		for (int q = 0; q < m; q++) {
			s[q] = new Segment(iread() - 1, iread() - 1);
			s2[q] = s[q];
		}
		Arrays.sort(s);

		for (int i = 0; i <= n; i++) {
			if (cur[i] != n) {
				add(cur[i], a[cur[i]].next, 1);
			}
		}

		int k = 0;
		for (int i = 0; i < n; i++) {
			while (k < m && s[k].l == i) {
				s[k].ans = get(s[k].r);
				k++;
			}

			int v = a[i].x;
			if (v <= n && cur[v] != n) {
				add(cur[v], a[cur[v]].next, -1);
				cur[v] = a[cur[v]].next;
				if (cur[v] != n) {
					add(cur[v], a[cur[v]].next, 1);
				}
			}
		}
		for (int i = 0; i < m; i++)
			out.write(s2[i].ans + "\n");
	}

	int[] tree;
	int base;

	void add(int l, int r, int val) {
		l += base;
		r += base;
		while (l < r) {
			if (l % 2 == 1) {
				tree[l] += val;
				l++;
			}
			if (r % 2 == 1) {
				r--;
				tree[r] += val;
			}
			l /= 2;
			r /= 2;
		}
	}

	int get(int x) {
		int ans = 0;
		x += base;
		while (x > 0) {
			ans += tree[x];
			x /= 2;
		}
		return ans;
	}

	class Number implements Comparable<Number> {
		int x, pos, next;

		public Number(int x, int pos) {
			super();
			this.x = x;
			this.pos = pos;
		}

		@Override
		public int compareTo(Number o) {
			if (x != o.x)
				return x - o.x;
			return pos - o.pos;
		}
	}

	class Segment implements Comparable<Segment> {
		int l, r, ans;

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

		@Override
		public int compareTo(Segment o) {
			return l - o.l;
		}
	}

	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new BufferedWriter(new OutputStreamWriter(System.out));
			// in = new BufferedReader(new FileReader(filename+".in"));
			// out = new BufferedWriter(new FileWriter(filename+".out"));
			solve();
			out.flush();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	public int iread() throws Exception {
		return Integer.parseInt(readword());
	}

	public double dread() throws Exception {
		return Double.parseDouble(readword());
	}

	public long lread() throws Exception {
		return Long.parseLong(readword());
	}

	BufferedReader in;

	BufferedWriter out;

	public String readword() throws IOException {
		StringBuilder b = new StringBuilder();
		int c;
		c = in.read();
		while (c >= 0 && c <= ' ')
			c = in.read();
		if (c < 0)
			return "";
		while (c > ' ') {
			b.append((char) c);
			c = in.read();
		}
		return b.toString();
	}

	public static void main(String[] args) {
		try {
			Locale.setDefault(Locale.US);
		} catch (Exception e) {

		}
		// new Thread(new Main()).start();
		new Thread(null, new Main(), "1", 1 << 25).start();
	}
}