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

/*
TASK: littleelephantandarray
LANG: JAVA
 */
public class littleelephantandarray {
    static int n , m , sqrt;
    static int[][] a , quer;
    static int[] b , ans , c , num;
    public static void main(String[] args) throws IOException {
        FastScanner in = new FastScanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        sqrt = 316;
        a = new int[n][2];
        ans = new int[m];
        b = new int[n];
        c = new int[n];
        quer = new int[m][3];
        for(int i = 0;i < n; i++){
            a[i][0] = in.nextInt();
            a[i][1] = i;
        }
        Arrays.sort(a, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        int cnt = 0;
        b[a[0][1]] = 0;
        c[0] = a[0][0];
        for(int i = 1;i < n; i++){
            if(a[i][0] != a[i-1][0])cnt++;
            b[a[i][1]] = cnt;
            c[cnt] = a[i][0];
        }
        for(int i = 0;i < m; i++){
            quer[i][0] = in.nextInt()-1;
            quer[i][1] = in.nextInt()-1;
            quer[i][2] = i;
        }
        Arrays.sort(quer, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]/sqrt == o2[0]/sqrt)return o1[1] - o2[1];
                return o1[0]/sqrt  - o2[0]/sqrt;
            }
        });
        int cur = 0;
        int l = 0;
        int r = -1;
        num = new int[n];
        for(int i = 0; i < m; i++){
            while(r < quer[i][1]) cur += add(++r);
            while(r > quer[i][1]) cur += rem(r--);
            while(l < quer[i][0]) cur += rem(l++);
            while(l > quer[i][0]) cur += add(--l);
            ans[quer[i][2]] = cur;
        }
        for(int i = 0;i< m; i++){
            System.out.println(ans[i]);
        }
    }
    private static int add(int a){
        num[b[a]]++;
        if(num[b[a]] == c[b[a]])return 1;
        if(num[b[a]] == c[b[a]]+1)return -1;
        return 0;
    }
    private static int rem(int a){
        num[b[a]]--;
        if(num[b[a]] == c[b[a]])return 1;
        if(num[b[a]] == c[b[a]]-1)return -1;
        return 0;
    }
    private static class FastScanner {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public FastScanner(InputStream stream) {
            this.stream = stream;
        }

        int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) return -1;
            }
            return buf[curChar++];
        }

        boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        boolean isEndline(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }

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

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

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

        public String next() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public String nextLine() {
            int c = read();
            while (isEndline(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndline(c));
            return res.toString();
        }
    }
}
