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.util.Arrays;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
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;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskB solver = new TaskB();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskB {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();
            count a = new count(n);
            for (int i = 0; i < n; i++) a.a[i] = in.nextInt();
            p[] ps = new p[m];
            for (int i = 0; i < m; i++) {
                ps[i] = new p(in.nextInt(), in.nextInt(), i);
            }
            int sqrt = (int) Math.sqrt(n);
            Arrays.sort(ps, (p f, p s) -> (f.l / sqrt == s.l / sqrt) ? (f.r / sqrt - s.r / sqrt) : (f.l / sqrt - s.l / sqrt));
            int[] ans = new int[m];
            int l = 1;
            int r = 1;
            a.set(1);
            for (int i = 0; i < m; i++) {
                int curL = ps[i].l;
                int curR = ps[i].r;
                while (l < curL) {
                    a.rem(l);
                    l++;
                }
                while (l > curL) {
                    l--;
                    a.add(l);
                }
                while (r < curR) {
                    r++;
                    a.add(r);
                }
                while (r > curR) {
                    a.rem(r);
                    r--;
                }
                ans[ps[i].n] = a.count;
            }
            for (int i = 0; i < m; i++) out.println(ans[i]);
        }

        class p {
            int l;
            int r;
            int n;

            p(int l1, int r1, int n1) {
                l = l1;
                r = r1;
                n = n1;
            }

        }

        class count {
            int[] map = new int[1_000_001];
            int[] a;
            int count = 0;

            count(int n) {
                a = new int[n];
            }

            void set(int ind) {
                ind--;
                if (a[ind] <= 1000000) {
                    map[a[ind]]++;
                    if (map[a[ind]] == a[ind]) count++;
                }
            }

            void add(int ind) {
                ind--;
                if (a[ind] <= 1000000) {
                    map[a[ind]]++;
                    if (map[a[ind]] == a[ind]) count++;
                    else if (map[a[ind]] == a[ind] + 1) count--;
                }
            }

            void rem(int ind) {
                ind--;
                if (a[ind] <= 1000000) {
                    map[a[ind]]--;
                    if (map[a[ind]] == a[ind]) count++;
                    else if (map[a[ind]] == a[ind] - 1) count--;
                }
            }

        }

    }

    static class InputReader {
        private StringTokenizer tokenizer;
        private BufferedReader reader;

        public InputReader(InputStream inputStream) {
            reader = new BufferedReader(new InputStreamReader(inputStream));
        }

        private void fillTokenizer() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (Exception e) {
                    throw new RuntimeException(e);
                }
            }
        }

        public String next() {
            fillTokenizer();
            return tokenizer.nextToken();
        }

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

    }
}

