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.util.Map.Entry;
import java.lang.*;
import java.io.*;
import java.math.BigInteger;


public class CF {
	private static FS sc = new FS();
	
	private static class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());				               
	            } catch (IOException e) {}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
	
	private static class extra {
		
		static int[] intArr(int size) {
			int[] a = new int[size];
			for(int i = 0; i < size; i++) a[i] = sc.nextInt();
			return a;
		}
		
		static long[] longArr(int size) {
			long[] a = new long[size];
			for(int i = 0; i < size; i++) a[i] = sc.nextLong();
			return a;
		}
		
		static long intSum(int[] a) {
			long sum = 0; 
			for(int i = 0; i < a.length; i++) {
				sum += a[i];
			}
			return sum;
		}
		
		static long longSum(long[] a) {
			long sum = 0; 
			for(int i = 0; i < a.length; i++) {
				sum += a[i];
			}
			return sum;
		}
		
		static LinkedList[] graphD(int vertices, int edges) {
			LinkedList<Integer>[] temp = new LinkedList[vertices+1];
			for(int i = 0; i <= vertices; i++) temp[i] = new LinkedList<>();
			for(int i = 0; i < edges; i++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				temp[x].add(y);
			}
			return temp;
		}
		
		static LinkedList[] graphUD(int vertices, int edges) {
			LinkedList<Integer>[] temp = new LinkedList[vertices+1];
			for(int i = 0; i <= vertices; i++) temp[i] = new LinkedList<>();
			for(int i = 0; i < edges; i++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				temp[x].add(y);
				temp[y].add(x);
			}
			return temp;
		}
		
		static void printG(LinkedList[] temp) {
			for(LinkedList<Integer> aa:temp) System.out.println(aa);
		}
		
		static long cal(long val, long pow) {
			if(pow == 0) return 1;
			long res = cal(val, pow/2);
			
//			long ret = (res*res)%mod;
//			if(pow%2 == 0) return ret;
//			return (val*ret)%mod;
			long ret = res*res;
			if(pow%2 == 0) return ret;
			return val*ret;
		}
		
		static long gcd(long a, long b) { return b == 0 ? a:gcd(b, a%b); }
		
	}
	
	static int mod = (int) 1e9 + 9;
//	static int mod = (int) 998244353;
	static int max = (int) 1e5+5, sq = 316;
	static LinkedList<Integer>[] temp;
//	static int[][] pre;
	static int ans;
	
	static class pair {
		int l, r, idx;
		pair(int x, int y, int z) {
			l = x; r = y; idx = z;
		}
	}
	
	public static void main(String[] args) {	
//		int t = sc.nextInt();
		int t = 1;
		StringBuilder ret = new StringBuilder();
		while(t-- > 0) {
			int n = sc.nextInt();
			int q = sc.nextInt();
			int[] a = extra.intArr(n);
			pair[] p = new pair[max];
			for(int i = 0; i < max; i++) p[i] = new pair(0,0,0);
			for(int i = 0; i < q; i++) {
				int l = sc.nextInt();
				int r = sc.nextInt();
				p[i] = new pair(l, r, i);
			}
			Arrays.sort(p, new Comparator<pair>() {

				@Override
				public int compare(pair o1, pair o2) {
					if(o1.l/sq == o2.l/sq) return o1.r - o2.r;
					return o1.l - o2.l;
				}
				
			});
			
			ans = 0;
			int[] f = new int[max];
			int[] an = new int[q];
			int x = 0, y = -1;
			for(int i = max-q; i < max; i++) {
				while(y < p[i].r-1) operate(++y, 1, f, a);
				while(x > p[i].l-1) operate(--x, 1, f, a);
				
				while(y > p[i].r-1) operate(y--, -1, f, a);
				while(x < p[i].l-1) operate(x++, -1, f, a);
				an[p[i].idx] = ans;
			}
			for(int aa:an) ret.append(aa + "\n"); 
 		}
		System.out.println(ret);
	}
	
	static void operate(int idx, int op, int[] f, int[] a) {
		int x = a[idx];
		if(x >= max) return ;
		if(f[x] == x) ans--;
		f[x] += op;
		if(f[x] == x) ans++;
	}
}