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.util.*;
import java.lang.reflect.Array;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

public class  Main  {
	
	//ArrayList<Integer> lis = new ArrayList<Integer>();
	//ArrayList<String> lis = new ArrayList<String>();
	//ArrayList<test> lis = new ArrayList<test>();
//	static long sum=0;
//	static boolean f=false;
	//static String s[],r="";
//	static int dx[]={1,-1,0,0,1,1,-1,-1};
  //  static int dy[]={0,0,1,-1,1,-1,1,-1},n,m,w=0;
//	static int N;
//	static boolean b[][],c[],h;
public  static void main(String[] args)  {
   //googlein.txt C-small-attempt0.in
//	Scanner sc =new Scanner(new File("file.txt"));
	 Scanner sc =new Scanner(System.in);
	  //File file = new File("file.txt");
	//	PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(file)));
	//	sc.useDelimiter("(\\s)+|[,]");
		 
	  while(sc.hasNext()){
		   //long sum=0;
		//  int n=sc.nextInt(),m=sc.nextInt(),l=sc.nextInt(),r=0;
	   
		  int n=sc.nextInt(),m=sc.nextInt(),y[]=new int[max(500,n)],x[]=new int[n+1],z[][]=new int[m][2],r[]=new int[m];
		  for(int i=0;i<n;i++)y[i]=sc.nextInt();
		  for(int i=0;i<n;i++)if(y[i]<=n)x[y[i]]++;
		
		  int  d[]=new int[n],f[]=new int[500];
		  for(int i=1,j=0;i<=n;i++) if(i<=x[i]){ f[j]=i; j++; } 
		  for(int i=0;i<m;i++){
			  z[i][0]=sc.nextInt(); z[i][1]=sc.nextInt();
		  }
		  
		  for(int i=0;i<500;i++){
			  d=new int[n+1];
			  for(int t=0;t<n;t++){
				  d[t+1]+=( f[i]==y[t]? 1:0)+d[t] ;
			  }
			 // db(d);
			  for(int t=0;t<m;t++){
				if(0<f[i] && d[z[t][1]]-d[z[t][0]-1]==f[i] )r[t]++;  
			  }
			  
		  }
		  for(int t=0;t<m;t++)System.out.println(r[t]);
	  
          }
	  
	  }
	// db("Case #"+(k)+": "+c);
	 //	pw.println("Case #"+(k)+": "+c);
	 	
	 	//pw.flush();
	 	//pw.close();   
	
   

    static void db(Object... os){
	         System.err.println(Arrays.deepToString(os));
 
	}

}
/*
class P {
    int v,vv,c;
	P(int v,int vv,int c){
		this.v=v;
	    this.vv=vv;
	    this.c=c;
	} 	
 

}
*/