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.InputStreamReader;
import java.io.FileNotFoundException;
import java.io.File;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.BufferedReader;
import java.io.UnsupportedEncodingException;
import java.io.InputStream;

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

    static class LittleElephantAndArray {
        int sqrt = 1;
        int[] ans;
        int[] arr;
        int n;
        int count = 0;
        int[] map = new int[1000000];

        void add(int idx) {
            if (arr[idx] > 1000000) return;
            map[arr[idx]]++;
            if (map[arr[idx]] == arr[idx]) ++count;
            if (map[arr[idx]] == arr[idx] + 1) --count;
        }

        void remove(int idx) {
            if (arr[idx] > 1000000) return;
            map[arr[idx]]--;
            if (map[arr[idx]] == arr[idx]) ++count;
            if (map[arr[idx]] == arr[idx] - 1) --count;
        }

        public void solve(int testNumber, FastReader in, OutputWriter out) {
            n = in.nextInt();
            int q = in.nextInt();
            arr = in.nextIntArray(n);
            ans = new int[q];
            Query[] queries = new Query[q];
            sqrt = (int) Math.sqrt(n) + 1;
            for (int i = 0; i < q; i++) {
                int f = in.nextInt() - 1;
                int t = in.nextInt() - 1;
                queries[i] = new Query(f, t, i);
            }
            Arrays.sort(queries);
            int l = 1, r = 0;
            for (int i = 0; i < q; i++) {
                int curL = queries[i].f;
                int curR = queries[i].t;
                while (r < curR) {
                    add(++r);
                }
                while (r > curR) {
                    remove(r--);
                }
                while (l > curL) {
                    add(--l);
                }
                while (l < curL) {
                    remove(l++);
                }
                ans[queries[i].id] = count;
            }
            for (int i = 0; i < q; i++) out.println(ans[i]);
        }

        class Query implements Comparable<Query> {
            int f;
            int t;
            int id;

            public Query(int f, int t, int id) {
                this.f = f;
                this.t = t;
                this.id = id;
            }


            public int compareTo(Query o) {
                int cmp = Integer.compare(f / sqrt, o.f / sqrt);
                if (cmp == 0) return Integer.compare(t, o.t);
                return cmp;
            }


            public String toString() {
                return "Query{" +
                        "f=" + f +
                        ", t=" + t +
                        ", id=" + id +
                        '}';
            }

        }

    }

    static class FastReader {
        BufferedReader reader;
        StringTokenizer st;

        public FastReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            st = null;
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String line = reader.readLine();
                    if (line == null) {
                        return null;
                    }
                    st = new StringTokenizer(line);
                } catch (Exception e) {
                    throw new RuntimeException();
                }
            }
            return st.nextToken();
        }

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

        public int[] nextIntArray(int n) {
            int[] arr = new int[n];
            int i = 0;
            while (i < n) {
                arr[i++] = nextInt();
            }
            return arr;
        }

    }

    static class OutputWriter extends PrintWriter {
        public OutputWriter(OutputStream os, boolean autoFlush) {
            super(os, autoFlush);
        }

        public OutputWriter(Writer out) {
            super(out);
        }

        public OutputWriter(Writer out, boolean autoFlush) {
            super(out, autoFlush);
        }

        public OutputWriter(String fileName) throws FileNotFoundException {
            super(fileName);
        }

        public OutputWriter(String fileName, String csn) throws FileNotFoundException, UnsupportedEncodingException {
            super(fileName, csn);
        }

        public OutputWriter(File file) throws FileNotFoundException {
            super(file);
        }

        public OutputWriter(File file, String csn) throws FileNotFoundException, UnsupportedEncodingException {
            super(file, csn);
        }

        public OutputWriter(OutputStream out) {
            super(out);
        }


        public void flush() {
            super.flush();
        }


        public void close() {
            super.close();
        }

    }
}

