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;

public class ProblemB {
    
    static final int MAX_NUM = 100000;
    
    public static void main(String[] args) throws IOException {
        BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        
        String[] line = s.readLine().split(" ");
        int n = Integer.valueOf(line[0]);
        int m = Integer.valueOf(line[1]);
        
        int[] a = new int[n];
        String[] data = s.readLine().split(" "); 
        for (int i = 0 ; i < n ; i++) {
            a[i] = Integer.valueOf(data[i]);
        }
        
        int[] cnt = new int[MAX_NUM+1];
        for (int i = 0 ; i < n ; i++) {
            if (a[i] <= MAX_NUM) {
                cnt[a[i]]++;
            }
        }
        
        int[] pnum = new int[501];
        int pidx = 0;
        for (int i = 1 ; i <= MAX_NUM ; i++) {
            if (cnt[i] >= i) {
                pnum[pidx++] = i;
            }
        }
        
        int[][] qdata = new int[m][2];
        for (int q = 0 ; q < m ; q++) {
            String[] qi = s.readLine().split(" ");
            qdata[q][0] = Integer.valueOf(qi[0]);;
            qdata[q][1] = Integer.valueOf(qi[1]);;
        }
        
        int[] qans = new int[m];
        for (int i = 0 ; i < pidx ; i++) {
            int[] sum = new int[n+1];
            for (int j = 0 ; j < n ; j++) {
                sum[j+1] += sum[j] + ((a[j] == pnum[i]) ? 1 : 0);
            }
            for (int q = 0 ; q < m ; q++) {
                if (sum[qdata[q][1]] - sum[qdata[q][0]-1] == pnum[i]) {
                    qans[q]++;
                }
            }
        }
        
        for (int q = 0 ; q < m ; q++) {
            out.println(qans[q]);
        }
        out.flush();
    }
}