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.Arrays;
import java.util.StringTokenizer;

/**
 * Created by peacefrog on 3/7/16.
 * 11:00 PM
 */
public class CF220B {
	final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
	PrintWriter out;
	long timeBegin, timeEnd;

	public void runIO() throws IOException {
		timeBegin = System.currentTimeMillis();

		InputStream inputStream;
		OutputStream outputStream;

		if (ONLINE_JUDGE) {
			inputStream = System.in;
			Reader.init(inputStream);
			outputStream = System.out;

			out = new PrintWriter(outputStream);
		} else {
			inputStream = new FileInputStream("/home/peacefrog/Dropbox/IdeaProjects/Problem Solving/input");
			Reader.init(inputStream);
			out = new PrintWriter(System.out);
		}
		solve();
		out.flush();
		out.close();
		timeEnd = System.currentTimeMillis();
		System.err.println("Time = " + (timeEnd - timeBegin));
	}

	/*
	 * Start Solution Here
	 */

	int sq ;
	private static final int a = 123456;
	int cnt[] , arr[] , answer , currentL , currentR;

	public void add(int position)
	{
		if(arr[position]> 1E6) return;
		cnt[arr[position]]++;
		if(cnt[arr[position]]==arr[position])answer++;
		else if(cnt[arr[position]]==(arr[position]+1)) answer--;
	}
	public void remove(int position)
	{
		if(arr[position]> 1E6) return;
		cnt[arr[position]]--;
		if(cnt[arr[position]]==arr[position])answer++;
		else if(cnt[arr[position]]==(arr[position]-1)) answer--;
	}

	private void solve() throws IOException {
		//Use  out
		int n = Reader.nextInt(),q = Reader.nextInt();
		arr= Reader.nextIntArray(n);
		cnt = new int[a];

		int result[] = new int[q];
		query[] queries = new query[q];
		sq = (int) Math.sqrt(n);

		for (int i = 0; i < q; i++) {
			queries[i] = new query(Reader.nextInt()-1 , Reader.nextInt()-1 , i );
		}
		Arrays.sort(queries);

//		for (int i = 0; i < q; i++) {
//
//			System.out.println(queries[i].l + " " + queries[i].r + " " + queries[i].index) ;
//		}
		for (int i = 0; i < q; i++) {
			int l = queries[i].l , r = queries[i].r , in = queries[i].index;

			while (currentL < l){
				remove(currentL);
				currentL++;
			}
			while (currentL > l){
				currentL--;
				add(currentL);
			}

			while (currentR <= r){
				add(currentR);
				currentR++;
			}
			while (currentR > r+1)
			{
				currentR--;
				remove(currentR);
			}

			result[in] = answer;
		}

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

	}

	class query implements Comparable<query>{
		int l , r , index;

		public query(int l, int r, int index) {
			this.l = l;
			this.r = r;
			this.index = index;
		}

		@Override
		public int compareTo(query o) {
			int res = Integer.compare( l/sq ,o.l/sq );
			if(res != 0 ) return res;
			else return Integer.compare( r/sq , o.r/sq );
		}
	}

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

	static class Reader {
		static BufferedReader reader;
		static StringTokenizer tokenizer;

		/**
		 * call this method to initialize reader for InputStream
		 */
		static void init(InputStream input) {
			reader = new BufferedReader(new InputStreamReader(input));
			tokenizer = new StringTokenizer("");
		}

		/**
		 * get next word
		 */
		static String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		static String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return "";
		}

		static int nextChar() throws IOException {
			return reader.read();
		}

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

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

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

		static long[] nextLongArray(int n) throws IOException {
			long[] arr = new long[n];
			for (int i = 0; i < n; i++) {
				arr[i] = nextLong();
			}

			return arr;
		}

		static int[] nextIntArray(int n) throws IOException {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = nextInt();
			}
			return arr;
		}
	}
}