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.awt.*;
import java.awt.geom.Point2D;
import java.io.*;
import java.util.*;
import java.util.List;


public class Main {

    private static InputReader sc = new InputReader(System.in);
    private static PrintWriter pw = new PrintWriter(System.out);
    private static long timeBegin;
    private static long memoryTotal;

    static int[] arr;
    static Query[] q;
    static long ans;
    static long[] qans;
    static Map<Integer, Integer> count;

    public static void main(String [] args) {
        timeBegin = System.currentTimeMillis();
        memoryTotal = Runtime.getRuntime().freeMemory();


        int n = sc.nextInt();
        int t = sc.nextInt();
        arr = new int[n];
        count = new HashMap<>();
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            count.put(arr[i], 0);
        }

        ans = 0;
        q = new Query[t];
        Query.nsqrt = (int) (Math.sqrt(n));
        qans = new long[t];

        for (int i = 0; i < t; i++) {
            int l = sc.nextInt() - 1;
            int r = sc.nextInt() - 1;
            q[i] = new Query(l, r, i);
        }

        int block = Query.nsqrt;

        Arrays.sort(q, (Query x, Query y) -> {
            if (x.l / block != y.l / block) return x.l / block - y.l / block;
            return x.r - y.r;
        });

        int left = 0;
        int right = -1;

        for (int i = 0; i < t; i++) {
            while (left < q[i].l) remove(arr[left++]);
            while (left > q[i].l) add(arr[--left]);
            while (right < q[i].r) add(arr[++right]);
            while (right > q[i].r) remove(arr[right--]);
            qans[q[i].id] = ans;
        }

        for (long x : qans) pw.println(x);





        checker();
        terminate();
    }

    static void add(int val) {
        Integer num = count.get(val);
        if (num == val) --ans;
        ++num;
        count.put(val, num);
        if (num == val) ++ans;
    }

    static void remove(int val) {
        Integer num = count.get(val);
        --num;
        count.put(val, num);
        if (num == val - 1) --ans;
        else if (num == val) ++ans;
    }


    static class Query {
        int l;
        int r;
        int id;
        static int nsqrt;

        public Query(int l, int r, int id) {
            this.l = l;
            this.r = r;
            this.id = id;
        }

    }



    public static void checker() {
        if (System.getProperty("ONLINE_JUDGE") == null) {
            System.out.println();
            time();
            memory();
        }
    }
    public static void time() {
        long timeEnd = System.currentTimeMillis();
        System.err.println("Time = " + (timeEnd - timeBegin));
    }
    public static void memory() {
        long memoryFree = Runtime.getRuntime().freeMemory();
        System.err.println("Memory = " + ((memoryTotal - memoryFree) >> 10)
                + " KB");
    }
    public static void terminate() {
        pw.close();
    }

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

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

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

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

    }
}

