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 Test3 implements Runnable {

    public static class Interval implements Comparable{

        int idx;
        int start;
        int end;

        @Override
        public int compareTo(Object o) {
            return this.start - ((Interval)o).start;
        }
    }



    void solve() throws IOException {
        int n = readInt();
        int m = readInt();

        int result[] = new int[m];
        Interval[] query = new Interval[m];

        long arr[] = new long[n];
        for(int i = 0 ;i < n ; i ++) {
            arr[i] = readLong();
        }


        for(int i = 0 ; i < m ; i ++) {
            int start = readInt();
            int end   = readInt();
            query[i] = new Interval();
            query[i].start = start;
            query[i].end   = end;
            query[i].idx   = i;

        }

        Map<Long,Long> map = new HashMap<Long,Long>();
        for(long x:arr) {
            if(!map.containsKey(x))
                map.put(x,1L);
            else
                map.put(x, map.get(x) + 1);
        }

        Set<Long> valid = new HashSet<Long>();
        for(long key:map.keySet()) {
            long value = map.get(key) ;
            if(value >= key)
                valid.add(key);
        }

        int dp[] = new int[n];
        for(long x:valid) {
            Arrays.fill(dp, 0);
            for(int i = 0 ; i < n ;i ++) {
                if(arr[i] == x)
                    dp[i] = 1;
                if(i != 0)
                    dp[i] += dp[i-1];

                if(dp[i] < x)
                    continue;

            }

            for(Interval interval:query) {
                long value = dp[interval.end - 1];
                if(interval.start != 1)
                    value -= dp[interval.start-2];
                if(value == x)
                    result[interval.idx] ++;
            }
        }

        for(int i = 0 ; i < result.length ; i ++) {
            out.println(result[i]);
        }

    }



    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

    public static void main(String[] args) {
        new Test3().run();
    }

    public void run() {
        try {
            long t1 = System.currentTimeMillis();
            if (System.getProperty("ONLINE_JUDGE") != null) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            }
            Locale.setDefault(Locale.US);
            solve();
            in.close();
            out.close();
            long t2 = System.currentTimeMillis();
            System.err.println("Time = " + (t2 - t1));
        } catch (Throwable t) {
            t.printStackTrace(System.err);
            System.exit(-1);
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }


}