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.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;

public class Main {
	public static int SQRT;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		String line = br.readLine();
		String[] split = line.split(" ");
		int N = Integer.parseInt(split[0]);
		SQRT = (int) Math.sqrt(N);
		int Q = Integer.parseInt(split[1]);
		
		line = br.readLine();
		split = line.split(" ");
		int[] arr = new int[N];
		for(int i = 0; i<N; i++) arr[i] = Integer.parseInt(split[i]);
		
		Query[] sortedQueries = new Query[Q];
		Query[] unsortedQueries = new Query[Q];
		for(int i = 0; i<Q; i++){
			line = br.readLine();
			split = line.split(" ");
			int L = Integer.parseInt(split[0]);
			int R = Integer.parseInt(split[1]);
			Query qq = new Query(L-1, R-1);
			sortedQueries[i] = qq;
			unsortedQueries[i] = qq;
		}
		Arrays.sort(sortedQueries);
		
		HashMap<Integer, Integer> occurances = new HashMap<>();
		occurances.put(arr[0], 1);
		int total = 0;
		if(arr[0] == 1) total = 1;
		int currentL = 0;
		int currentR = 0;
		for(Query q : sortedQueries){
			//MOVE R
			while(q.R < currentR){
				//move currentR left
				int occ = occurances.get(arr[currentR]);
				if(arr[currentR] == occ) total--;
				else if(arr[currentR] == (occ-1)) total++;
				occurances.put(arr[currentR], occ - 1);
				currentR--;
			}
			while(q.R > currentR){
				//move currentR right
				currentR++;
				Integer occ = occurances.get(arr[currentR]);
				if(occ == null) occ = 0;
				if(arr[currentR] == occ) total--;				
				else if(arr[currentR] == (occ+1)) total++;
				occurances.put(arr[currentR], occ + 1);
			}
			
			//MOVE L
			while(q.L < currentL){
				//move currentL left
				currentL--;
				Integer occ = occurances.get(arr[currentL]);
				if(occ == null) occ = 0;
				if(arr[currentL] == occ) total--;
				else if(arr[currentL] == (occ+1)) total++;
				occurances.put(arr[currentL], occ + 1);
			}
			while(q.L > currentL){
				//move currentL right
				int occ = occurances.get(arr[currentL]);
				if(arr[currentL] == occ) total--;
				else if(arr[currentL] == (occ-1)) total++;
				occurances.put(arr[currentL], occ - 1);
				currentL++;
			}
			q.ans = total;
		}
		for(Query q : unsortedQueries){
			sb.append(q.ans);
			sb.append("\n");
		}
		System.out.print(sb);
	}
}

class Query implements Comparable<Query>{
	int L;
	int R;
	int bucket;
	int ans;
	Query(int l, int r){
		L = l;
		R = r;
		bucket = L / Main.SQRT;
	}
	
	@Override
	public int compareTo(Query q) {
		int dif = bucket - q.bucket;
		if(dif == 0) return R - q.R;
		return dif;
	}
}