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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Round136B {

	public static final int block_size = 350;
	
	public static long[] freq;
	public static int ans;
	public static final int max = (int)1e5+10;
	
	public static void Add(int val) {
		if(val >= max) return;
		if(freq[val] == val) ans--;
		freq[val]++;
		if(freq[val] == val) ans++;
	}
	public static void Remove(int val) {
		if(val >= max) return;
		if(freq[val] == val) ans--;
		freq[val]--;
		if(freq[val] == val) ans++;
	}
	
	public static void solve() {
		int n = s.nextInt();
		int m = s.nextInt();
		int[] arr = new int[n];
		for(int i = 0; i < n; i++) arr[i] = s.nextInt();
		freq = new long[max];
		ans = 0;
		Query[] given = new Query[m];
		for(int i = 0; i < m; i++) {
			int l = s.nextInt() - 1;
			int r = s.nextInt() - 1;
			given[i] = new Query(l, r, i);
		}
		Arrays.sort(given);
		int currL = 0, currR = -1;
		long[] answers = new long[m];
		for(int i = 0; i < m; i++) {
			int qL = given[i].l;
			int qR = given[i].r;
			while(currL < qL) {
				Remove(arr[currL]);
				currL++;
			}
			while(currL > qL) {
				currL--;
				Add(arr[currL]);
			}
			while(currR < qR) {
				currR++;
				Add(arr[currR]);
			}
			while(currR > qR) {
				Remove(arr[currR]);
				currR--;
			}
			answers[given[i].idx] = ans;
		}
		for(int i = 0; i < m; i++) {
			out.println(answers[i]);
		}
	}

	public static void main(String[] args) {
		out = new PrintWriter(new BufferedOutputStream(System.out));
		s = new FastReader();
		solve();
		out.close();
	}
	
	public static class Query implements Comparable<Query>{
		int l, r, idx, block_id;
		public Query(int l, int r, int idx) {
			this.l = l;
			this.r = r;
			this.idx = idx;
			block_id = l/block_size;
		}
		public int compareTo(Query x) {
			if(this.block_id == x.block_id) {
				return this.r - x.r;
			}else {
				return this.block_id - x.block_id;
			}
		}
	}

	public static FastReader s;
	public static PrintWriter out;

	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

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

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

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

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception e) {
				e.printStackTrace();
			}
			return str;
		}
	}

	
}
