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

public class LittleElephantAndArray {
    public static class FastScanner {

        BufferedReader br;
        StringTokenizer st;

        public FastScanner(String s) {
            try {
                br = new BufferedReader(new FileReader(s));
            } catch (FileNotFoundException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String nextToken() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

        long nextLong() {
            return Long.parseLong(nextToken());
        }

        double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }


    private static Map<Integer, Integer> map;
    private static int answer = 0;

    // true when it adds one
    private static void add(int value) {
        Integer res = map.get(value);
        if (res == null) {
            res = 0;
        }
        map.put(value, res + 1);
        if (value == res + 1) {
            answer++;
        }
        if (value == res) {
            answer--;
        }
    }

    // true when it removes an actual answer
    private static void remove(int value) {
//        System.out.println("Remove!: " + value);
        Integer res = map.get(value);
        if (res == null) {
            return;
        }
        map.put(value, res - 1);
        if (res == value) {
            answer--;
        }
        if (res == value + 1) {
            answer++;
        }
    }


    public static void main(String[] args) {
        map = new HashMap<>();
        FastScanner fs = new FastScanner();
        int n = fs.nextInt();
        int m = fs.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = fs.nextInt();
        }

        int[] solutions = new int[m];
        Query[] queries = new Query[m];
        for (int i = 0; i < m; ++i) {
            int l = fs.nextInt() - 1;
            int r = fs.nextInt();
            queries[i] = new Query(l, r, i);
        }


        int sq = (int) Math.sqrt(n);

        Arrays.sort(queries, (o1, o2) -> {
            // check if they are on the same block??
            int r = o1.l / sq - o2.l / sq;
            if (r == 0) {
                return o1.r - o2.r;
            }
            return r;
        });


        int currentL = 0, currentR = 0;
        for (int i = 0; i < m; ++i) {
            int l = queries[i].l;
            int r = queries[i].r;

            while (currentL > l) {
                currentL--;
                add(a[currentL]);
            }

            while (currentR < r) {
                add(a[currentR]);
                currentR++;
            }

            while (currentL < l) {
                remove(a[currentL]);
                currentL++;
            }

            while (currentR > r) {
                currentR--;
                remove(a[currentR]);
            }

            solutions[queries[i].order] = answer;
        }

        StringBuffer sb = new StringBuffer();
        for(int i = 0; i < m; i++) {
            sb.append(solutions[i]);
            sb.append('\n');
        }

        System.out.println(sb);
    }

    private static class Query {
        int l, r, order;
        public Query(int l, int r, int o) {
            this.l = l;
            this.r = r;
            this.order = o;
        }
    }
}
