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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.OutputStream;
import java.util.Arrays;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedOutputStream;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Kattio in = new Kattio(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskDIV1B solver = new TaskDIV1B();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskDIV1B {
        public void solve(int testNumber, Kattio in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();

            int blockSize = (int) Math.sqrt(n);
            int[] arr = new int[n];
            for (int i = 0; i < n; ++i) {
                arr[i] = in.nextInt();
                if (arr[i] > (int) 1e5) arr[i] = (int) 1e5 + 1;
            }

            int[][] q = new int[m][3];
            for (int i = 0; i < m; ++i) {
                q[i][0] = in.nextInt() - 1;
                q[i][1] = in.nextInt() - 1;
                q[i][2] = i;
            }

            Arrays.sort(q, (q1, q2) -> {
                if (q1[0] / blockSize != q2[0] / blockSize) {
                    return q1[0] - q2[0];
                }

                return q1[1] - q2[1];
            });

            int[] ans = new int[m];
            int cnt = 0;
            int[] occs = new int[(int) 1e5 + 2];

            int l = 0;
            int r = 0;
            for (int i = 0; i < m; ++i) {

                while (l < q[i][0]) {
                    int x = arr[l++];
                    if (occs[x] - 1 == x) ++cnt;
                    else if (occs[x] == x) --cnt;
                    --occs[x];
                }

                while (l > q[i][0]) {
                    int x = arr[--l];
                    if (occs[x] + 1 == x) ++cnt;
                    else if (occs[x] == x) --cnt;
                    ++occs[x];
                }

                while (r <= q[i][1]) {
                    int x = arr[r++];
                    if (occs[x] + 1 == x) ++cnt;
                    else if (occs[x] == x) --cnt;
                    ++occs[x];
                }

                while (r > q[i][1] + 1) {
                    int x = arr[--r];
                    if (occs[x] - 1 == x) ++cnt;
                    else if (occs[x] == x) --cnt;
                    --occs[x];
                }

                ans[q[i][2]] = cnt;
            }

            for (int i = 0; i < m; ++i)
                out.println(ans[i]);

        }

    }

    static class Kattio extends PrintWriter {
        private BufferedReader r;
        private String line;
        private StringTokenizer st;
        private String token;

        public Kattio(InputStream i) {
            super(new BufferedOutputStream(System.out));
            r = new BufferedReader(new InputStreamReader(i));
        }

        public Kattio(InputStream i, OutputStream o) {
            super(new BufferedOutputStream(o));
            r = new BufferedReader(new InputStreamReader(i));
        }

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

        private String peekToken() {
            if (token == null)
                try {
                    while (st == null || !st.hasMoreTokens()) {
                        line = r.readLine();
                        if (line == null) return null;
                        st = new StringTokenizer(line);
                    }
                    token = st.nextToken();
                } catch (IOException e) {
                }
            return token;
        }

        private String nextToken() {
            String ans = peekToken();
            token = null;
            return ans;
        }

    }
}

