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.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.TreeSet;
import java.io.Writer;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskB solver = new TaskB();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskB {
	public void solve(int testNumber, InputReader in, OutputWriter out) {
	    int n = in.nextInt(), m = in.nextInt();
        int i,j,k;
        int a[] = in.nextIntArray(n);
        int ans[] = new int[m];
        int left[] = new int[m];
        int right[] = new int[m];

        for(int q = 0; q<m; ++q){
            left[q] = in.nextInt()-1;
            right[q] = in.nextInt()-1;
        }
        
        int cnt[] = new int[n+1];
        
        for(i = 0;i<n;++i) if(a[i]<=n) cnt[a[i]]++;
        
        TreeSet<Integer> set = new TreeSet<Integer>();
        for(i=0;i<n;++i) if(a[i]<=n && a[i]<=cnt[a[i]]) set.add(a[i]);
        
        int candidates[] = new int[set.size()];
        i = 0;
        for(Integer x : set) candidates[i++] = x; 
        
        
        for(k = 0; k<candidates.length; ++k){
            int s[] = new int[n+1];
            for(i=0;i<n;++i) if(a[i]==candidates[k]) s[i] = 1;
            for(i=n-1; i>=0; --i) s[i] = s[i]+s[i+1];
            
            for(j=0;j<m;++j) if(s[left[j]] - s[right[j]+1] == candidates[k]) ++ans[j];
        }
        
        out.write(ans);
    }
}

class InputReader{
    private BufferedReader reader;
    private StringTokenizer tokenizer;
    
    public InputReader(InputStream stream){
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }
    
    public String next(){
        while(tokenizer==null || !tokenizer.hasMoreTokens()){
            try{
                tokenizer = new StringTokenizer(reader.readLine());
            }catch(Exception e){
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }
    
    public int nextInt(){
        return Integer.parseInt(next());
    }

    public int[] nextIntArray(int size){
        int array[] = new int[size];
        for(int i=0; i<size; ++i) array[i] = nextInt();
        return array;
    }
}

class OutputWriter{
    private PrintWriter out;
    
    public OutputWriter(Writer out){
        this.out = new PrintWriter(out);
    }

    public OutputWriter(OutputStream out){
        this.out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(out)));
    }
    
    public void close(){
        out.flush();
        out.close();
    }

    public void write(int a[]){
        for(int i=0;i<a.length;++i){
            if(i>0) out.print(' ');
            out.print(a[i]);
        }
    }
}

