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.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Binary_Operations  {

	static int n;
	static int q;

	static int BLOCK_SIZE;
	
	static int[] freq = new int[1000001];
	static int[] arr;

	static int sum = 0;
	
	public static void main(String[] args) throws Exception {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		String[] line = in.readLine().split("\\s+");
		
		 n = Integer.parseInt(line[0]);
		 q = Integer.parseInt(line[1]);
		
		 BLOCK_SIZE = (int)Math.sqrt(n);
		 
		arr = new int[n];
		
		line = in.readLine().split("\\s+");
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(line[i]);
		}
		
		List<int[]> list = new ArrayList<>();
		
		for(int i=0; i<q; i++) {
			line = in.readLine().split("\\s+");
			
			list.add(new int[]{Integer.parseInt(line[0])-1, Integer.parseInt(line[1])-1, i});
		}
		
		Collections.sort(list, new Qcomp(BLOCK_SIZE));
		
		int l = 0;
		int r = -1;
		
		int[] ans = new int[q];
		
		for(int i=0; i<list.size(); i++) {
			int[] cur = list.get(i);
			
			
			while(l > cur[0]) {
				l--;
				add(l);
			}
			
			while(r < cur[1]) {
				r++;
				add(r);
			}
			
			while(l < cur[0]) {
				remove(l);
				l++;
			}
			
			while(r > cur[1]) {
				remove(r);
				r--;
			}
			
			ans[cur[2]] = sum;
			
		}
		
		PrintWriter out = new PrintWriter(System.out);
		
		for(int i : ans) {
			out.println(i);
		}
		
		out.close();
			
	}

	private static void remove(int i) {
		if(arr[i] > 1000000) {
			return;
		}
		if(freq[arr[i]] == arr[i]) {
			sum--;
		}
		else if(freq[arr[i]] == arr[i] + 1) {
			sum++;
		}
		
		freq[arr[i]]--;
	}

	private static void add(int i) {
		if(arr[i] > 1000000) {
			return;
		}
		if(freq[arr[i]] == arr[i]) {
			sum--;
		}
		else if(freq[arr[i]] == arr[i] - 1) {
			sum++;
		}
		
		freq[arr[i]]++;
		
	}

}

class Qcomp implements Comparator<int[]> {

	int BLOCK_SIZE;

	Qcomp(int sz) {
		BLOCK_SIZE = sz;
	}

	public int compare(int[] o1, int[] o2) {
		if(o1[0] / BLOCK_SIZE == o2[0] / BLOCK_SIZE) {
			return Integer.compare(o1[1], o2[1]);
		}
		else {
			return Integer.compare(o1[0] / BLOCK_SIZE, o2[0] / BLOCK_SIZE);
		}
	}
} 