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 temp{
    static HashMap<Integer, Integer> hm = new HashMap<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
        int arr[] = new int[x];
        query qry[] = new query[q];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < x; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            qry[i] = new query(Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())-1);

        }
        for (int i = 0; i < x; i++) {
            if(hm.get(arr[i]) == null || hm.get(arr[i]) != -1) {
                add(arr[i]);
                if (hm.get(arr[i]) >= arr[i]) {
                    int pfix[] = new int[x];
                    for (int j = 0; j < x; j++) {
                        pfix[j] = arr[j] == arr[i] ? 1 : 0;
                        if (j != 0) {
                            pfix[j] += pfix[j - 1];
                        }
                    }
                    for (int k = 0; k < q; k++)
                        if (pfix[qry[k].r] - (qry[k].l != 0 ? pfix[qry[k].l-1] : 0) == arr[i])
                            qry[k].ans++;
                    hm.put(arr[i], -1);
                }
            }
        }
        for(query qr : qry)
            System.out.println(qr.ans);
    }
    public static void add(int x){
        if(!hm.containsKey(x))
            hm.put(x, 1);
        else
            hm.put(x, hm.get(x) + 1);
    }
    static class query{
        int l;
        int r;
        int ans = 0;
        public query(int l, int r) {
            this.l = l;
            this.r = r;
        }
    }
}
