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

/* 
Keep solving problems. 
*/
import java.util.*;
import java.io.*;

public class CF220B {

    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;
    final long MOD = 1000L * 1000L * 1000L + 7;
    int SQRT;
    class Query implements Comparable<Query> {
        int left;
        int right;
        int idx;
        long pair;

        int start;
        public Query(int left, int right, int idx) {
            this.left = left;
            this.right = right;
            this.idx = idx;
            pair = 0;
            start = this.left / SQRT;
        }

        @Override
        public int compareTo(Query o) {
            if(this.start != o.start) {
                return o.start - this.start;
            }
            else {
                return this.right - o.right;
            }

        }
        public String toString() {
            return "left: " + left + ", right: " + right;
        }
    }
    void solve() throws IOException {
        int n = nextInt();
        int m = nextInt();
        int[] arr = nextIntArr(n);
//        int n = 100000;
//        int m = 100000;
//        int[] arr = new int[n];
//        Random rdm = new Random();
//        for(int i = 0; i < n; i++) {
//            arr[i] = i + 1;
//        }
        SQRT = (int) Math.sqrt(n);

        Query[] list = new Query[m];
        for(int i = 0; i < m; i++) {
            list[i] = new Query(nextInt() - 1, nextInt() - 1, i);
//            int l = rdm.nextInt(10000);
//            int r = rdm.nextInt(10000);
//            list[i] = new Query(Math.min(l, r), Math.max(l, r), i);
        }

        Arrays.sort(list);
        int l = 0;
        int r = -1;
        int len = 100000 + 10;
        int[] hist = new int[len];

        long tmp = 0;
        for(Query q : list) {
            int left = q.left;
            int right = q.right;

            while(r < right) {//note the order
                r++;
                int v = arr[r];
                if(v < len) {
                    if (hist[v] == v) {
                        tmp--;
                    }
                    hist[v]++;
                    if (hist[v] == v) {
                        tmp++;
                    }
                }
            }

            while(r > right) {//note the order
                int v = arr[r];
                if(v < len) {
                    if (hist[v] == v) {
                        tmp--;
                    }
                    hist[v]--;
                    if (hist[v] == v) {
                        tmp++;
                    }
                }
                r--;
            }

            while(l < left) {//note the order
                int v = arr[l];
                if(v < len) {
                    if (hist[v] == v) {
                        tmp--;
                    }
                    hist[v]--;
                    if (hist[v] == v) {
                        tmp++;
                    }
                }
                l++;
            }

            while(l > left) {//note the order
                l--;
                int v = arr[l];
                if(v < len) {
                    if (hist[v] == v) {
                        tmp--;
                    }
                    hist[v]++;
                    if (hist[v] == v) {
                        tmp++;
                    }
                }
            }
            q.pair = tmp;
        }

        long[] res = new long[m];
        for(Query q : list) {
            res[q.idx] = q.pair;
        }

        for(int i = 0; i < m; i++) {
            outln(res[i]);
        }
    }

    void shuffle(int[] a) {
        int n = a.length;
        for(int i = 0; i < n; i++) {
            int r = i + (int) (Math.random() * (n - i));
            int tmp = a[i];
            a[i] = a[r];
            a[r] = tmp;
        }
    }
    private void outln(Object o) {
        out.println(o);
    }
    private void out(Object o) {
        out.print(o);
    }
    public CF220B() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
//        long start = System.currentTimeMillis();
        solve();

//        long end = System.currentTimeMillis();
//        System.out.println("use (sec): " + (end - start) / 1000.0);
        out.close();
    }
    public static void main(String[] args) throws IOException {
        new CF220B();
    }

    public long[] nextLongArr(int n) throws IOException{
        long[] res = new long[n];
        for(int i = 0; i < n; i++)
            res[i] = nextLong();
        return res;
    }
    public int[] nextIntArr(int n) throws IOException {
        int[] res = new int[n];
        for(int i = 0; i < n; i++)
            res[i] = nextInt();
        return res;
    }
    public String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }
    public String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }
    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}

