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 file {
	public static int MOD = 1000000007;

	static Scan scn = new Scan();
	static Print printer = new Print();

	static int ans = 0;

	public static void main(String[] args) throws Exception {
		int n = scn.scanInt();
		int q = scn.scanInt();

		int[] arr = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			arr[i] = scn.scanInt();
		}
		query.sqrt = (int) Math.sqrt(n) + 1;
		query[] qrs = new query[q];
		int[] fans = new int[q];
		for (int i = 0; i < qrs.length; i++) {
			qrs[i] = new query(i, scn.scanInt(), scn.scanInt());
		}
		Arrays.sort(qrs);

		int[] freq = new int[(int) 1e5 + 5];
		int left = 0, right = -1;
		for (query qr : qrs) {
			int st = qr.st;
			int ed = qr.ed;

			while (left < st) {
				remove(freq, arr[left++]);

			}

			while (left > st) {
				add(freq, arr[--left]);

			}

			while (right > ed) {
				remove(freq, arr[right--]);
			}

			while (right < ed) {
				add(freq, arr[++right]);
			}
			fans[qr.id] = ans;
		}

		for (int val : fans) {
			printer.printLine(val + "");
		}

		printer.close();

	}

	public static void add(int[] freq, int val) {

		if (val > freq.length - 1)
			return;

		freq[val]++;

		if (freq[val] == val)
			ans++;
		else if (freq[val] == val + 1)
			ans--;
	}

	public static void remove(int[] freq, int val) {

		if (val > freq.length - 1)
			return;

		freq[val]--;

		if (freq[val] == val)
			ans++;
		else if (freq[val] == val - 1)
			ans--;
	}

	public static class query implements Comparable<query> {
		int st;
		int ed;
		int id;
		static int sqrt;

		public query(int id, int st, int ed) {
			this.st = st;
			this.ed = ed;
			this.id = id;
		}

		@Override
		public int compareTo(query o) {
			if (st / sqrt - o.st / sqrt != 0)
				return st / sqrt - o.st / sqrt;
			return ed - o.ed;
		}
	}

	static class Scan {
		private InputStream in;
		private byte[] buf = new byte[1024 * 1024];
		private int index;
		private int total;

		public Scan() {
			// this.in = in;
			in = System.in;
			// try {
			// in = new FileInputStream(new File("/home/ujjwal/test/test"));
			// } catch (Exception ex) {
			//
			// }
		}

		public int scan() throws IOException {
			if (total < 0)
				throw new InputMismatchException();
			if (index >= total) {
				index = 0;
				total = in.read(buf);
				if (total <= 0)
					return -1;
			}
			return buf[index++];
		}

		public int scanInt() throws IOException {
			int integer = 0;
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			int neg = 1;
			if (n == '-') {
				neg = -1;
				n = scan();
			}
			while (!isWhiteSpace(n)) {
				if (n >= '0' && n <= '9') {
					integer *= 10;
					integer += n - '0';
					n = scan();
				} else
					throw new InputMismatchException();
			}
			return neg * integer;
		}

		public long scanLong() throws IOException {
			long integer = 0;
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			int neg = 1;
			if (n == '-') {
				neg = -1;
				n = scan();
			}
			while (!isWhiteSpace(n)) {
				if (n >= '0' && n <= '9') {
					integer *= 10;
					integer += n - '0';
					n = scan();
				} else
					throw new InputMismatchException();
			}
			return neg * integer;
		}

		public double scanDouble() throws IOException {
			double doub = 0;
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			int neg = 1;
			if (n == '-') {
				neg = -1;
				n = scan();
			}
			while (!isWhiteSpace(n) && n != '.') {
				if (n >= '0' && n <= '9') {
					doub *= 10;
					doub += n - '0';
					n = scan();
				} else
					throw new InputMismatchException();
			}
			if (n == '.') {
				n = scan();
				double temp = 1;
				while (!isWhiteSpace(n)) {
					if (n >= '0' && n <= '9') {
						temp /= 10;
						doub += (n - '0') * temp;
						n = scan();
					} else
						throw new InputMismatchException();
				}
			}
			return doub * neg;
		}

		public String scanString() throws IOException {
			StringBuilder sb = new StringBuilder();
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			while (!isWhiteSpace(n)) {
				sb.append((char) n);
				n = scan();
			}
			return sb.toString();
		}

		private boolean isWhiteSpace(int n) {
			if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1)
				return true;
			return false;
		}
	}

	static class Print {
		private final BufferedWriter bw;

		public Print() {
			bw = new BufferedWriter(new OutputStreamWriter(System.out));
		}

		public void print(String str) throws IOException {
			bw.append(str);
		}

		public void printLine(String str) throws IOException {
			print(str);
			bw.append("\n");
		}

		public void close() throws IOException {
			bw.close();
		}
	}

}
