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.util.*;
import java.io.*;
public class Main {
public static void main(String [] args)throws Exception{
	
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
	StringTokenizer st = new StringTokenizer(br.readLine());
	
	int n = Integer.parseInt(st.nextToken());
	int m = Integer.parseInt(st.nextToken());
	
	st = new StringTokenizer(br.readLine());
	
	int array [] = new int[n + 1];
	
	for(int i = 1;i <= n;i++)
		array[i]= Integer.parseInt(st.nextToken());
		
		int start [] = new int[m];
		int end[] = new int[m];
		
	for(int i = 0;i < m;i++){
		st = new StringTokenizer(br.readLine());
		
		start[i] = Integer.parseInt(st.nextToken());
		end[i] = Integer.parseInt(st.nextToken());
	}
	
	int cnt [] = new int[n + 1];
	for(int i = 1;i <= n;i++){
		if(array[i] > n)continue;
		cnt[array[i]]++;
	}
	int ans [] = new int[m];
	
	for(int i = 1;i <= n;i++){
		if(cnt[i] < i)continue;
		int temp [] = new int[n + 1];
		for(int j = 1;j <= n;j++){
			temp[j] = temp[j - 1];
			if(array[j] == i)temp[j]++; 
		}
		for(int j = 0;j < m;j++){
			if(temp[end[j]] - temp[start[j] - 1] == i)ans[j]++;
		}
	}
	StringBuilder sb = new StringBuilder();
	for(int i = 0;i < m;i++){
		sb.append(ans[i]);
		sb.append('\n');
	}
	System.out.println(sb);
}
}