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.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import java.util.StringTokenizer;


public class D136 {	
	BufferedReader reader;
    StringTokenizer tokenizer;
    PrintWriter out;

	public void solve() throws IOException {
		int MAX = 100000;
		int N = nextInt();
		int M = nextInt();
		
		int[] counter = new int[N+1];
		int[] a = new int[N];
		for(int i = 0; i < N; i++){
			a[i] = nextInt();
			if( a[i] <= N ){
				counter[a[i]]++; 
			}
		}
		
		int[] l = new int[M];
		int[] r = new int[M];
		for(int i = 0; i < M; i++){
			l[i] = nextInt()-1;
			r[i] = nextInt()-1;			
		}	
		
		int[] ans = new int[M];
		for(int i = 1; i <= N; i++){
			if( counter[i] < i) continue;
			int[] dp = new int[N];
			dp[0] = a[0]==i?1:0;
			for(int j = 1; j < N; j++){
				dp[j] = dp[j-1] + (a[j]==i?1:0);
			}
			for(int j = 0; j < M; j++){
				if( dp[r[j]] - (l[j]>0? dp[ l[j]-1 ]:0) == i){
					ans[j]++;
				}
			}
		}
		for(int j = 0; j < M; j++){
			out.println( ans[j] );
		}			
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		new D136().run();
	}
	
	public void run() {
        try {
            reader = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = null;
            out = new PrintWriter(System.out);
            solve();
            reader.close();
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    String nextToken() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

}
