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.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;


public class Main {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++)
            a[i] = sc.nextInt();
        FenwickTree ft = new FenwickTree(n);
        Query[] queries = new Query[m];
        for (int i = 0; i < m; i++)
            queries[i] = new Query(i, sc.nextInt(), sc.nextInt());
        int[] ans = new int[m];
        HashMap<Integer, HashMap<Integer, Integer>> locations = new HashMap<>();
        HashMap<Integer, Integer> occ = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            if (!locations.containsKey(a[i])) locations.put(a[i], new HashMap<>());
            int last = occ.getOrDefault(a[i], 0);
            if (last == a[i] - 1) ft.update(i, 1);
            if (last == a[i]) ft.update(i, -1);
            locations.get(a[i]).put(last + 1, i);
            occ.put(a[i], last + 1);
        }
        Arrays.sort(queries);
        int L = 1;
        occ = new HashMap<>();
        for (int i = 0; i < m; i++) {
            while (L < queries[i].left) {
                int remove = a[L];
                int seen = occ.getOrDefault(remove, 0);
                int old = seen + remove;
                if (locations.get(remove).containsKey(old)) ft.update(locations.get(remove).get(old), -1);
                if (locations.get(remove).containsKey(old + 1)) ft.update(locations.get(remove).get(old + 1), 2);
                if (locations.get(remove).containsKey(old + 2)) ft.update(locations.get(remove).get(old + 2), -1);
                occ.put(remove, seen + 1);
                L++;
            }
            ans[queries[i].idx] = ft.rsq(queries[i].left, queries[i].right);
        }
        for (int x : ans)
            out.println(x);
        out.close();
        out.flush();

    }

    static class Query implements Comparable<Query> {
        int idx, left, right;

        public Query(int idx, int left, int right) {
            this.idx = idx;
            this.left = left;
            this.right = right;
        }

        @Override
        public int compareTo(Query o) {
            return left - o.left;
        }
    }

    static class FenwickTree {
        int n;
        int[] ft;

        public FenwickTree(int n) {
            this.n = n;
            ft = new int[n + 1];
        }

        void update(int idx, int val) {
            while (idx <= n) {
                ft[idx] += val;
                idx += idx & -idx;
            }
        }

        int rsq(int idx) {
            int sum = 0;
            while (idx > 0) {
                sum += ft[idx];
                idx -= idx & -idx;
            }
            return sum;
        }

        int rsq(int a, int b) {
            return rsq(b) - rsq(a - 1);
        }
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream system) {
            br = new BufferedReader(new InputStreamReader(system));
        }

        public Scanner(String file) throws Exception {
            br = new BufferedReader(new FileReader(file));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

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

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public char nextChar() throws IOException {
            return next().charAt(0);
        }

        public Long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public boolean ready() throws IOException {
            return br.ready();
        }

        public void waitForInput() throws InterruptedException {
            Thread.sleep(3000);
        }

        public int[] nextIntArray(int n) throws IOException {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public long[] nextLongArray(int n) throws IOException {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }


        public Integer[] nextIntegerArray(int n) throws IOException {
            Integer[] a = new Integer[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public double[] nextDoubleArray(int n) throws IOException {
            double[] ans = new double[n];
            for (int i = 0; i < n; i++)
                ans[i] = nextDouble();
            return ans;
        }

        public short nextShort() throws IOException {
            return Short.parseShort(next());
        }

    }

}