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

	void run() throws IOException {
		int n = cin.nextInt(), Q = cin.nextInt();

		int ar[] = new int[n], sum[] = new int[n];
		int app[] = new int[n + 1];

		for (int i = 0; i < n; ++i) {
			ar[i] = cin.nextInt();
			if (ar[i] <= n)
				++app[ar[i]];
		}

		int l[] = new int[Q], r[] = new int[Q], ans[] = new int[Q];
		for (int i = 0; i < Q; ++i) {
			l[i] = cin.nextInt() - 1;
			r[i] = cin.nextInt() - 1;
		}

		for (int i = 1; i <= n; ++i)
			if (app[i] >= i) {
				if (ar[0] == i)
					sum[0] = 1;
				else
					sum[0] = 0;
				for (int j = 1; j < n; ++j) {
					sum[j] = sum[j - 1];
					if (ar[j] == i)
						++sum[j];
				}

				for (int j = 0; j < Q; ++j) {
					if (l[j] == 0) {
						if (sum[r[j]] - 0 == i)
							++ans[j];
						continue;
					}
					if (sum[r[j]] - sum[l[j] - 1] == i)
						++ans[j];
				}
			}

		for (int i = 0; i < Q; ++i)
			out.println(ans[i]);
		out.close();
	}

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

	Main() {
		cin = new InputReader(System.in);
		// cin = new Scanner(System.in);
		out = new PrintWriter(System.out);
	}

	PrintWriter out;
	InputReader cin;

	// Scanner cin;

	class InputReader {
		InputReader(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			// try {
			// reader = new BufferedReader(new FileReader("E.in"));
			// } catch (FileNotFoundException ex) {
			// }
			tokenizer = new StringTokenizer("");
		}

		private String next() throws IOException {
			while (!tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}
			return tokenizer.nextToken();
		}

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

		private BufferedReader reader;
		private StringTokenizer tokenizer;
	}
}
 	 	  		        	  		   	 	