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.*;
import java.math.*;

public class B {
	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer st;
	static Random rnd;

	class Query {
		int l, r, id;

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

	class SegmentTree {
		int[] value, push;

		public SegmentTree(int size) {
			value = new int[4 * size];
			push = new int[4 * size];
		}

		private final int left(int v) {
			return (v << 1);
		}

		private final int right(int v) {
			return (v << 1) + 1;
		}

		private final int middle(int l, int r) {
			return (l + r) >> 1;
		}

		public void change(int v, int l, int r, int tl, int tr, int diff) {
			if (l == tl && r == tr) {
				value[v] += diff;
				push[v] += diff;
			} else {
				push(v);

				int m = middle(l, r);

				if (tl <= m)
					change(left(v), l, m, tl, Math.min(tr, m), diff);

				if (tr > m)
					change(right(v), m + 1, r, Math.max(m + 1, tl), tr, diff);
			}
		}

		public int get(int v, int l, int r, int ind) {
			if (l == r) {
				return value[v];
			} else {
				push(v);

				int m = middle(l, r);

				if (ind <= m)
					return get(left(v), l, m, ind);
				else
					return get(right(v), m + 1, r, ind);
			}
		}

		private void push(int v) {
			if (push[v] != 0) {
				push[left(v)] += push[v];
				push[right(v)] += push[v];
				value[left(v)] += push[v];
				value[right(v)] += push[v];
				push[v] = 0;
			}
		}
	}

	void solve() throws IOException {
		int n = nextInt(), m = nextInt();

		int[] arr = new int[n];

		for (int i = 0; i < n; i++)
			arr[i] = nextInt();

		Query[] qs = new Query[m];

		for (int i = 0; i < m; i++)
			qs[i] = new Query(nextInt() - 1, nextInt() - 1, i);

		Arrays.sort(qs, new Comparator<Query>() {
			public int compare(Query a, Query b) {
				if (a.l != b.l)
					return Integer.signum(a.l - b.l);

				return Integer.signum(a.id - b.id);
			}
		});

		ArrayList<Integer>[] poses = new ArrayList[n + 1];

		for (int i = 0; i <= n; i++)
			poses[i] = new ArrayList<Integer>();

		int[] gone = new int[n + 1], res = new int[m];
		SegmentTree ans = new SegmentTree(n);

		int curAns = 0;

		for (int i = 0; i < n; i++) {
			if (arr[i] <= n) {
				poses[arr[i]].add(i);

				if (poses[arr[i]].size() == arr[i])
					++curAns;
				else if (poses[arr[i]].size() == arr[i] + 1)
					--curAns;
			}

			ans.change(1, 0, n - 1, i, i, curAns);
		}

		int qPtr = 0;

		//int[] temp = new int[n + 1], wtf = new int[m];

		for (int leftBorder = 0; leftBorder < n; leftBorder++) {
			/*{
				out.println("Debug ans: ");
				
				for(int i = 0; i < n; i++) {
					out.print(ans.get(1, 0, n - 1, i) + " ");
				}
				
				out.println("---");
			}*/
			
			while (qPtr < m && qs[qPtr].l == leftBorder) {

				res[qs[qPtr].id] = ans.get(1, 0, n - 1, qs[qPtr].r);

				/*{

					int dumb = 0;
					Arrays.fill(temp, 0);
					for (int i = leftBorder; i <= qs[qPtr].r; i++)
						if (arr[i] <= n)
							++temp[arr[i]];
					for (int i = 1; i <= n; i++)
						if (temp[i] == i)
							++dumb;

					wtf[qs[qPtr].id] = dumb;
				}*/

				++qPtr;
			}

			if (arr[leftBorder] <= n) {

				int firstRealPos = arr[leftBorder] + gone[arr[leftBorder]] - 1, secondRealPos = firstRealPos + 1, thirdRealPos = secondRealPos + 1;

				int firstIndex = -1, secondIndex = n, thirdIndex = n;

				if (poses[arr[leftBorder]].size() > firstRealPos)
					firstIndex = poses[arr[leftBorder]].get(firstRealPos);

				if (poses[arr[leftBorder]].size() > secondRealPos)
					secondIndex = poses[arr[leftBorder]].get(secondRealPos);

				if (poses[arr[leftBorder]].size() > thirdRealPos)
					thirdIndex = poses[arr[leftBorder]].get(thirdRealPos);
				
				//out.println("Debug: " + leftBorder + " " + arr[leftBorder] + " " +firstIndex + " " + secondIndex + " " + thirdIndex);

				if (firstIndex != -1) {
					ans.change(1, 0, n - 1, firstIndex, secondIndex - 1, -1);
					//out.println("Decrease: " + (firstIndex) + " " + (secondIndex - 1));

					if (secondIndex != n) {
						ans.change(1, 0, n - 1, secondIndex, thirdIndex - 1, 1);
						//out.println("Increase: " + (secondIndex) + " " + (thirdIndex - 1));
					}
				}

				++gone[arr[leftBorder]];
			}
		}

		for (int i = 0; i < m; i++) {
			out.println(res[i]);
		}
	}

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

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

			rnd = new Random();

			solve();

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

	String nextToken() throws IOException {
		while (st == null || !st.hasMoreTokens()) {
			String line = in.readLine();

			if (line == null)
				return null;

			st = new StringTokenizer(line);
		}

		return st.nextToken();
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

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