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.*;

import static java.lang.Math.*;

public class Main implements Runnable {
	
	int ceil(int[] arr, int val) {
		int l = -1, r = arr.length;
		while (r - l > 1) {
			int m = l + (r - l) / 2;
			if (arr[m] < val) {
				l = m;
			} else {
				r = m;
			}
		}
		return r;
	}
	
	int floor(int[] arr, int val) {
		int l = -1, r = arr.length;
		while (r - l > 1) {
			int m = l + (r - l) / 2;
			if (arr[m] > val) {
				r = m;
			} else {
				l = m;
			}
		}
		return l;
	}
	
	class Segment {
		int index;
		int l, r;
		int lans = -1, rans = -1;
		
		public Segment(int index, int l, int r) {
			this.index = index;
			this.l = l;
			this.r = r;
		}
		
		@Override
		public String toString() {
			return "[" + l + "; " + r + "]";
		}
	}
	
	void solve() throws Exception {
		long start = System.currentTimeMillis();
		int n = sc.nextInt(), m = sc.nextInt();
		int[] a = new int[n];
		Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
		int curnum = 1;
		int curc = 0;
		Random rnd = new Random();
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
			/*
			a[i] = curnum;
			curc++;
			if (curc == curnum) {
				curc = 0;
				curnum++;
			}
			*/
			if (!cnt.containsKey(a[i])) {
				cnt.put(a[i], 0);
			}
			cnt.put(a[i], cnt.get(a[i]) + 1);
		}
		Map<Integer, int[]> positions = new HashMap<Integer, int[]>();
		Map<Integer, Integer> curpos = new HashMap<Integer, Integer>();
		for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
			if (e.getValue() < e.getKey()) {
				continue;
			}
			positions.put(e.getKey(), new int[e.getValue()]);
			curpos.put(e.getKey(), 0);
		}
		for (int i = 0; i < n; i++) {
			if (positions.containsKey(a[i])) {
				int[] arr = positions.get(a[i]);
				int pos = curpos.get(a[i]);
				arr[pos++] = i;
				curpos.put(a[i], pos);
			}
		}
		int[] l = new int[m], r = new int[m];
		int[] answer = new int[m];
		Segment[] byL = new Segment[m], byR = new Segment[m];
		for (int i = 0; i < m; i++) {
			l[i] = sc.nextInt() - 1;
			r[i] = sc.nextInt() - 1;
			//r[i] = rnd.nextInt(n);
			//l[i] = rnd.nextInt(r[i] + 1);
			byL[i] = byR[i] = new Segment(i, l[i], r[i]);
		}
		Arrays.sort(byL, new Comparator<Segment>() {
			@Override
			public int compare(Segment s1, Segment s2) {
				return s1.l - s2.l;
			}
		});
		Arrays.sort(byR, new Comparator<Segment>() {
			@Override
			public int compare(Segment s1, Segment s2) {
				return s1.r - s2.r;
			}
		});
		if (System.currentTimeMillis() - start > 500) {
			//return;
		}
		for (Map.Entry<Integer, int[]> e : positions.entrySet()) {
			//for (int i = 0; i < m; i++) {
			//	byL[i].lans = byL[i].rans = -1;
			//}
			int num = e.getKey();
			int[] arr = e.getValue();
			int poss = 0;
			for (int i = 0; i < arr.length; i++) {
				while (poss < m && byL[poss].l <= arr[i]) {
					byL[poss++].lans = i;
				}
			}
			while (poss < m) {
				byL[poss++].lans = arr.length;
			}
			poss = m - 1;
			for (int i = arr.length - 1; i >= 0; i--) {
				while (poss >= 0 && byR[poss].r >= arr[i]) {
					byR[poss].rans = i;
					Segment seg = byR[poss];
					if (seg.rans - seg.lans + 1 == num) {
						answer[seg.index]++;
					}
					poss--;
				}
			}
			while (poss >= 0) {
				byR[poss].rans = -1;
				Segment seg = byR[poss];
				if (seg.rans - seg.lans + 1 == num) {
					answer[seg.index]++;
				}
				poss--;
			}
		}
		for (int i = 0; i < m; i++) {
			out.println(answer[i]);
		}
	}
	
	BufferedReader in;
	PrintWriter out;
	FastScanner sc;
	
	static Throwable uncaught;
	
	@Override
	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			sc = new FastScanner(in);
			solve();
		} catch (Throwable t) {
			Main.uncaught = t;
		} finally {
			out.close();
		}
	}
	
	public static void main(String[] args) throws Throwable {
		Thread t = new Thread(null, new Main(), "", 128 * 1024 * 1024);
		t.start();
		t.join();
		if (uncaught != null) {
			throw uncaught;
		}
	}

}

class FastScanner {
	
	BufferedReader reader;
	StringTokenizer strTok;
	
	public FastScanner(BufferedReader reader) {
		this.reader = reader;
	}
	
	public String nextToken() throws IOException {
		while (strTok == null || !strTok.hasMoreTokens()) {
			strTok = new StringTokenizer(reader.readLine());
		}
		return strTok.nextToken();
	}
	
	public int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}
	
	public long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}
	
	public double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
	
}