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.IOException;
import java.util.*;
public class cf_220B_Little_Elephant_and_Array {

	static int mod = (int) 1e9 + 7;
	static ArrayList<Integer> gr[];
	static int ar[];
	static Scanner sc = new Scanner(System.in);
	static int pri[] = new int[(int) 1e6 + 5];
	static StringBuilder out = new StringBuilder();

	public static class pair implements Comparable<pair> {
		int id;
		int f;
		int s;

		pair(int x, int y) {

			f = x;
			s = y;

		}

		pair(int i, int x, int y) {

			id = i;
			f = x;
			s = y;

		}

		public pair() {

		}

		public int compareTo(pair o) {
			// TODO Auto-generated method stub

			if (this.f / block != o.f/block)
				return this.f - o.f;
			return this.s-o.s;
			//return ((this.f/block)%2!=0)?(this.s-o.s):(o.s-this.s);
//			return this.f-o.f;       //sort according to first value;
//			return this.s-o.s;      //sort according to second value
//			return this.id - o.id;  //sort according to id 

		}
	}

	static int block = 0;
	static HashMap<Integer, Integer> hm = new HashMap<>();

	static void forl(int[] a, int s, int e) {
		for (int i = s; i < e; i++) {
			a[i] = sc.nextInt();
		}
	}

	static void add(int a) {
		int n=ar.length;
		if(a>n)return;
	    if(dp[a]==a)ans--;
	    dp[a]++;
	    if(dp[a]==a)ans++;

	}

	static void remove(int a) {
		int n=ar.length;
		if(a>n)return;
	    if(dp[a]==a)ans--;
	    dp[a]--;
	    if(dp[a]==a)ans++;
	}

	static int ans = 0;
	static int dp[]=new int[1000000+5];
	static int val=1000000;

	public static void main(String[] args) throws IOException {

		int t = 1;// sc.nextInt();
		while (t-- > 0) {

			int n = sc.nextInt();
			int m = sc.nextInt();
			ar = new int[n];
			block = (int) Math.sqrt(n);
			int res[]=new int [m];
			pair q[] = new pair[m];
			for(int i=0;i<n;i++) {
				ar[i]=sc.nextInt();
			}
			
			for (int i = 0; i < m; i++) {
				int l = sc.nextInt();
				int r = sc.nextInt();

				l--;
				r--;
				q[i] = new pair(i, l, r);
			}
			
			Arrays.sort(q);
			int cl = 0;
			int cr = -1;
			for (pair qu : q) {
				int l = qu.f;
				int r = qu.s;
				while (cl > l) {
					cl--;
					add(ar[cl]);

				}
				while (cr < r) {
					cr++;
					add(ar[cr]);
				}
				while (cl < l) {
					remove(ar[cl]);
					cl++;
				}
				while (cr > r) {
					remove(ar[cr]);
					cr--;
				}
				
				res[qu.id]=ans;
				
			}

			for(int i=0;i<m;i++)out.append(res[i]+"\n");
		}
		System.out.println(out);

	}

}
