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.HashMap;
import java.util.Map.Entry;
import java.awt.*;
import static java.lang.Math.*;
import static java.lang.Integer.*;
@SuppressWarnings("unused")
public class round136D {

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        HashMap<Integer, Integer> count = new HashMap<>();
        String [] use = null;
        use = br.readLine().split(" ");
        int N = parseInt(use[0]);
        int M = parseInt(use[1]);
        use = br.readLine().split(" ");
        int [] in = new int [N];
        for(int i = 0 ; i < N ; ++i)
            in[i] = parseInt(use[i]);
        Point [] queries = new Point [M];
        for(int i = 0 ; i < M ; ++i){
            use = br.readLine().split(" ");
            queries[i] = new Point(parseInt(use[0]) - 1, parseInt(use[1]) - 1);
        }
        for(int i = 0 ; i < N ; ++i){
            Integer a = count.get(in[i]);
            if(a == null)
                count.put(in[i], 1);
            else
                count.put(in[i], a + 1);
        }
        int [] ans = new int [M];
        for(Entry<Integer, Integer> e : count.entrySet()){
            if(e.getValue() < e.getKey())
                continue;
            int [] cum = new int [N + 1];
            cum[0] = in[0] == e.getKey() ? 1 : 0;
            for(int i = 1 ; i < N ; ++i){
                cum[i] = cum[i - 1] + ((in[i] == e.getKey()) ? 1 : 0);
            }
            for(int i = 0 ; i < M ; ++i){
                int end = queries[i].y;
                int st = queries[i].x;
                if(cum[end] - (st == 0 ? 0 : cum[st - 1]) == e.getKey())
                    ++ans[i];
            }
        }
        for(int i = 0 ; i < M ; ++i)
            System.out.println(ans[i]);
        return;         
    }
}
