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.BufferedReader;
import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.TreeMap;




public class Main {

    static int B_S;
    static HashMap<Integer, Integer> map;
    static int ans;

    private static void add(int x) {
        int y = map.containsKey(x) ? map.get(x) : 0;
        
        y+=1;
        map.put(x, y);
        
        
        if(y == x+1){
            ans -= 1;
        }else if(y == x){
            ans+=1;
        }
    }

    private static void remove(int x) {
        int y = map.get(x);
        if(y <= x){
            
            if(y==x)   ans -= 1;
            y-=1;
            map.put(x, y);
            
        }else{
            y-=1;
            map.put(x, y);
            if(y == x) ans+=1;
        }
    }
    
    static class Query{
        int L;
        int R;
        int id;
        public Query(int L, int R, int id){
            this.L = L;this.R = R; this.id = id;
        }
    }
   
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new PrintWriter(System.out));
        
        
        String[] in = br.readLine().split(" ");
        int n = Integer.parseInt(in[0]);
        int q = Integer.parseInt(in[1]);
        
        int[] a = new int[n];
        in = br.readLine().split(" ");
        for(int i=0;i<n;i++)    a[i] = Integer.parseInt(in[i]);
        
        ans = 0;
        B_S = (int) Math.sqrt(n);
        
        Query[] Q = new Query[q];
        
        for(int i=0;i<q;i++){
            in = br.readLine().split(" ");
            int L = Integer.parseInt(in[0]);
            int R = Integer.parseInt(in[1]);
            L-=1;
            R-=1;
            
            Q[i] = new Query(L, R, i);
        }
        
        //mo order the query
        Arrays.sort(Q, new Comparator<Query>(){
            @Override
            public int compare(Query x, Query y) {
                int ml = x.L/B_S;
                int mr = y.L/B_S;
                
                if(ml != mr){
                    return ml-mr;
                }
                return x.R-y.R;
            }
        });
        
        int mo_L = 0;
        int mo_R = -1;
        map = new HashMap<>();
        
        int[] val = new int[q];
        
        for(int i=0;i<Q.length;i++){
            int L = Q[i].L;
            int R = Q[i].R;
            
            while(mo_R < R){
                mo_R+=1;
                add(a[mo_R]);
            }
            while(mo_R > R){
                remove(a[mo_R]);
                mo_R-=1;
            }
            while(mo_L < L){
                remove(a[mo_L]);
                mo_L +=1;
            }
            while(mo_L > L){
                mo_L-=1;
                add(a[mo_L]);
            }
            
            val[Q[i].id] = ans;
        }
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<q;i++){
            sb.append(val[i]+"\n");
        }
        System.out.println(sb.toString());
        //bw.close();
        
        
    }

    

    

   
}
