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.*;
import java.math.*;

public class Main {

    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st = null;
    static String nx() throws Exception {
        for (;st == null || !st.hasMoreTokens();){
            String k1 = in.readLine();
            if (k1 == null) return null;
            st = new StringTokenizer(k1);
        }
        return st.nextToken();
    }
    static int ni() throws Exception {
        return Integer.parseInt(nx());
    }

    public static void main(String[] args) throws Exception {
        int n1 = ni();
        int m1 = ni();
        int[] l1 = new int[n1];
        for (int i = 0; i < n1; l1[i++] = ni());
        int[] count = new int[n1 + 1];
        for (int e : l1) {
            if (e <= n1)
                count[e]++;
        }
        // px(l1);
        int goodno = 0;
        int[] good = new int[n1 + 1];
        int[] id = new int[n1 + 1];
        Arrays.fill(id, -1);
        for (int i = 1; i <= n1; i++) {
            if (count[i] >= i) {
                id[i] = goodno;
                good[goodno++] = i;
                
            }
        }
        // px(Arrays.copyOf(good, goodno));
        int[] exCount = new int[goodno * (n1 + 1)];
        for (int i = 0; i < n1; i++) {
            if (l1[i] <= n1 && count[l1[i]] >= l1[i])
                exCount[id[l1[i]] + (i + 1) * goodno]++;
        }
        for (int i = 0; i < goodno; i++) {
            for (int j = 1; j <= n1; j++) {
                exCount[i+ j * goodno] += exCount[i+(j - 1) * goodno];
            }
        }
        for (int i = 0; i < m1; i++) {
            int left = ni() - 1;
            int right = ni();
            int ans = 0;
            for (int j = 0; j < goodno; j++) {
//                int have = exCount[j * n1 + right]
//                        - (left == 0 ? 0 : exCount[j * n1 + left - 1]);
                // px(have, exCount[j][left], right == 0);
                if (exCount[j  + right * goodno] - exCount[j  + left * goodno] == good[j])
                    ans++;
            }
            out.println(ans);
        }

        out.flush();
    }

    static PrintWriter out = new PrintWriter(System.out);

    static void px(Object... objects) {
        System.out.println(Arrays.deepToString(objects));
    }
}