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.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.StringTokenizer;

public class CF_C {

	/**
	 * @param args
	 * @throws IOException
	 */

	public static void main(String[] args) throws IOException {
		BufferedReader scan = new BufferedReader(new InputStreamReader(
				System.in));
		StringTokenizer stoken;
		PrintWriter write = new PrintWriter(System.out);
		stoken = new StringTokenizer(scan.readLine());
		int element = Integer.parseInt(stoken.nextToken()), nquery = Integer
				.parseInt(stoken.nextToken());

		int[] value = new int[element + 1];

		int[] sumval = new int[element + 1];
		int[] left = new int[nquery], right = new int[nquery], result = new int[nquery];
		int[] accu = new int[element + 1];
		stoken = new StringTokenizer(scan.readLine());
		for (int n = 1; n <= element; n++) {
			value[n] = Integer.parseInt(stoken.nextToken());
			if (value[n] <= element) {
				accu[value[n]]++;
			}
		}

		for (int n = 0; n < nquery; n++) {
			stoken = new StringTokenizer(scan.readLine());
			left[n] = Integer.parseInt(stoken.nextToken());
			right[n] = Integer.parseInt(stoken.nextToken());
		}

		for (int n = 1; n <= element; n++) {
			if (accu[n] >= n) {	
				//System.out.print("["+n+"]");
				Arrays.fill(sumval, 0);
				
				for (int m = 1; m <= element; m++) {
					if (value[m] == n) {
						sumval[m] = sumval[m - 1] + 1;
					} else {
						sumval[m] = sumval[m - 1];
					}
					//System.out.print(" "+sumval[m]);
				}
				//System.out.println();
				for (int p = 0; p < nquery; p++) {
					if (sumval[right[p]] - sumval[left[p] - 1] == n) {
						result[p]++;
					}
				}
			}

		}

		for (int n = 0; n < nquery; n++) {
			write.println(result[n]);
		}
		write.close();

	}

}

class ArrayUtils {
	private static int[] tempInt = new int[0];

	public static int[] sort(int[] array, IntComparator comparator) {
		return sort(array, 0, array.length, comparator);
	}

	public static int[] sort(int[] array, int from, int to,
			IntComparator comparator) {
		ensureCapacityInt(to - from);
		System.arraycopy(array, from, tempInt, 0, to - from);
		sortImpl(array, from, to, tempInt, 0, to - from, comparator);
		return array;
	}

	private static void ensureCapacityInt(int size) {
		if (tempInt.length >= size)
			return;
		size = Math.max(size, tempInt.length << 1);
		tempInt = new int[size];
	}

	private static void sortImpl(int[] array, int from, int to, int[] temp,
			int fromTemp, int toTemp, IntComparator comparator) {
		if (to - from <= 1)
			return;
		int middle = (to - from) >> 1;
		int tempMiddle = fromTemp + middle;
		sortImpl(temp, fromTemp, tempMiddle, array, from, from + middle,
				comparator);
		sortImpl(temp, tempMiddle, toTemp, array, from + middle, to, comparator);
		int index = from;
		int index1 = fromTemp;
		int index2 = tempMiddle;
		while (index1 < tempMiddle && index2 < toTemp) {
			if (comparator.compare(temp[index1], temp[index2]) <= 0)
				array[index++] = temp[index1++];
			else
				array[index++] = temp[index2++];
		}
		if (index1 != tempMiddle)
			System.arraycopy(temp, index1, array, index, tempMiddle - index1);
		if (index2 != toTemp)
			System.arraycopy(temp, index2, array, index, toTemp - index2);
	}

}

interface IntComparator {
	public static final IntComparator DEFAULT = new IntComparator() {
		public int compare(int first, int second) {
			if (first < second)
				return -1;
			if (first > second)
				return 1;
			return 0;
		}
	};

	public int compare(int first, int second);
}
