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.StringTokenizer;


public class Main {
    static int s;

    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 = sc.nextIntArray(n);
        s = (int) (Math.sqrt(n));
        Query queries[] = new Query[m];
        for (int i = 0; i < m; i++)
            queries[i] = new Query(sc.nextInt() - 1, sc.nextInt() - 1, i);
        Arrays.sort(queries);
        int left = -1, right = -1;
        Counter cnt = new Counter(a);
        int[] ans = new int[m];
        for (int i = 0; i < m; i++) {
            int queryLeft = queries[i].l;
            int queryRight = queries[i].r;
            while (queryLeft < left)
                cnt.add(--left);
            while (queryRight < right)
                cnt.remove(right--);
            while (queryRight > right)
                cnt.add(++right);
            while (queryLeft > left)
                cnt.remove(left++);
            ans[queries[i].idx] = cnt.ans;
        }
        for (int x : ans)
            out.println(x);
        out.close();
        out.flush();

    }

    static class Counter {
        int[] cnt;
        boolean[] taken;
        int ans, n, a[];

        public Counter(int[] a) {
            n = a.length;
            cnt = new int[n + 1];
            taken = new boolean[n + 1];
            this.a = a;
        }

        void add(int idx) {
            int val = a[idx];
            if (val >= n + 1 || taken[idx]) return;
            taken[idx] = true;
            int oldocc = cnt[val]++;
            if (oldocc == val) ans--;
            if (oldocc == val - 1) ans++;

        }

        void remove(int idx) {
            if (idx == -1) return;
            int val = a[idx];
            if (val >= n + 1 || !taken[idx]) return;
            taken[idx]= false;
            int oldocc = cnt[val]--;
            if (oldocc == val) ans--;
            if (oldocc == val + 1) ans++;
        }


    }

    static class Query implements Comparable<Query> {
        int l, r, idx, leftBlock;


        public Query(int l, int r, int idx) {
            this.l = l;
            this.r = r;
            this.idx = idx;
            leftBlock = l / s;
        }

        @Override
        public int compareTo(Query o) {
            return leftBlock == o.leftBlock ? r - o.r : leftBlock - o.leftBlock;
        }

    }

    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());
        }

    }

}