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
/*
 *
 * CREATED BY : NAITIK V
 * 
 * 
 */

import java.util.*;

import java.io.*;
public class A		
{ 
			 static FastReader sc=new FastReader(); 
			 static long dp[][];
			 static int mod=1000000007;
			 static int max;
			 static int ans;
			 static int block_size;
			 static int F[]=new int[100001];
			 //static HashMap<Integer,Integer> map=new HashMap<Integer, Integer>();
			// static int map[]=new int[300001];
		     public static void main(String[] args)
		    {
			  PrintWriter out=new PrintWriter(System.out);
			  StringBuffer sb=new StringBuffer("");
			 
		  int ttt=1;
		//  ttt =i();
		    outer :while (ttt-- > 0) 
			{
		    	int n=i();
		    	int q=i();
		    	block_size=(int)Math.sqrt(n);
		    	int A[]=input(n);
		    	Tri P[]=new Tri[q];
		    	for(int i=0;i<q;i++) {
		    		int a=i()-1;
		    		int b=i()-1;
		    		P[i]=new Tri(a, b, i);
		    	}
		    	Arrays.sort(P);
		    	int R[]=new int[q];
		    	int l=0,u=-1;
		    	for(int i=0;i<q;i++) {
		    		int a=P[i].x;
		    		int b=P[i].y;
		    		
		    		int idx=P[i].z;
		    		while(u<b) {
		    			u++;
		    			
		    			add(A,u);
		    		}
		    		while(l>a) {
		    			l--;
		    			add(A,l);
		    		}
		    		
		    		while(u>b) {
		    			remove(A,u);
		    			u--;
		    		}
		    		while(l<a) {
		    			remove(A,l);
		    			l++;
		    		}
		    		R[idx]=ans;
		    		
		    		
		    	}
		    	for(int i=0;i<q;i++) {
		    		out.println(R[i]);
		    	}
		    	
		    	
		    	
		    	
	        	
			}
		   out.close();
		  // System.out.println(sb.toString());
		   
		   
		   //CHECK FOR N=1                    //CHECK FOR M=0
		    //CHECK FOR N=1                    //CHECK FOR M=0
		   	//CHECK FOR N=1
		   	//CHECK FOR N=1
		   	//CHECK FOR N=1
    }

			  private static void remove(int A[],int u) {
				  
				  int k=A[u];
				  if(k>A.length)
					  return;
				  if(k==F[k]) {
					  ans--;
					  F[k]--;
				  }
				  else {
					  F[k]--;
					  if(k==F[k])
						  ans++;
				  }
				  
				  
				
			}

			private static void add(int A[],int u) {
				int k=A[u];
				if(k>A.length)
					  return;
				if(F[k]==k) {
					ans--;
					F[k]++;
				}
				else {
					F[k]++;
					if(F[k]==k)
						ans++;
				}
			}

			static class Tri implements Comparable<Tri>
			     {
			    	 int x;
			    	 int y;
			    	 int z;
			    	 Tri(int x,int y,int z){
			    		 this.x=x;
			    		 this.y=y;
			    		 this.z=z;
			    		 
			    	 }
					@Override
					public int compareTo(Tri o) {
						if(this.x/block_size==o.x/block_size) {
			                if(this.y==o.y)return this.z-o.z;
			                return y-o.y;
			            }
			            return x/block_size-o.x/block_size;
			        }
			     }
			     
			     

		    







static class Pair implements Comparable<Pair>
   {
	   int x;
	   int y;
	  	 Pair(int x,int y){
	  		 this.x=x;
	  		 this.y=y;
	  	 }
	@Override
//	public int compareTo(Pair o) {
//		if(this.x>o.x)
//			return 1;
//		else if(this.x<o.x)
//			return -1;
//		else {
//			if(this.y<o.y)
//				return 1;
//			else if(this.y>o.y)
//				return -1;
//			else
//				return 0;
//		}
//	}
	
	
	public int compareTo(Pair o) {
			if (x > o.x) {
				return 1;
			}
			if (x < o.x) {
				return -1;
			}
			if (y > o.y) {
				return 1;
			}
			if (y < o.y) {
				return -1;
			}
			return 0;
		}
	
 }
static int[] input(int n) {
  	int A[]=new int[n];
  	   for(int i=0;i<n;i++) {
  		   A[i]=sc.nextInt();
  	   }
  	   return A;
     }
  static long[] inputL(int n) {
  	long A[]=new long[n];
  	   for(int i=0;i<n;i++) {
  		   A[i]=sc.nextLong();
  	   }
  	   return A;
     }
  static String[] inputS(int n) {
  	String A[]=new String[n];
  	   for(int i=0;i<n;i++) {
  		   A[i]=sc.next();
  	   }
  	   return A;
     }
  static long sum(int A[]) {
  	long sum=0;
  	for(int i : A) {
  		sum+=i;
  	}
  	return sum;
  }
  static long sum(long A[]) {
  	long sum=0;
  	for(long i : A) {
  		sum+=i;
  	}
  	return sum;
  }

  static void input(int A[],int B[]) {
  	   for(int i=0;i<A.length;i++) {
  		   A[i]=sc.nextInt();
  		   B[i]=sc.nextInt();
  	   }
  }
  static int[][] input(int n,int m){
  	int A[][]=new int[n][m];
  	for(int i=0;i<n;i++) {
  		for(int j=0;j<m;j++) {
  			A[i][j]=i();
  		}
  	}
  	return A;
  }
  static char[][] charinput(int n,int m){
  	char A[][]=new char[n][m];
  	for(int i=0;i<n;i++) {
  		String s=s();
  		for(int j=0;j<m;j++) {
  			A[i][j]=s.charAt(j);
  		}
  	}
  	return A;
  }
  static int max(int A[]) {
  	int max=Integer.MIN_VALUE;
  	for(int i=0;i<A.length;i++) {
  		max=Math.max(max, A[i]);
  	}
  	return max;
  }
  static int min(int A[]) {
  	int min=Integer.MAX_VALUE;
  	for(int i=0;i<A.length;i++) {
  		min=Math.min(min, A[i]);
  	}
  	return min;
  }
  static long max(long A[]) {
  	long max=Long.MIN_VALUE;
  	for(int i=0;i<A.length;i++) {
  		max=Math.max(max, A[i]);
  	}
  	return max;
  }
  static long min(long A[]) {
  	long min=Long.MAX_VALUE;
  	for(int i=0;i<A.length;i++) {
  		min=Math.min(min, A[i]);
  	}
  	return min;
  }
  static long mod(long x) {
  	 int mod=1000000007;
  	  return ((x%mod + mod)%mod);
  }
  static String reverse(String s) {
  	StringBuffer p=new StringBuffer(s);
  	p.reverse();
  	return p.toString();
  }

       static int i() {
      	 return sc.nextInt();
       }
       static String s() {
      	 return sc.next();
       }
       static long l() {
      	 return sc.nextLong();
       }  
       static void sort(int[] A){
          int n = A.length;
          Random rnd = new Random();
          for(int i=0; i<n; ++i){
              int tmp = A[i];
              int randomPos = i + rnd.nextInt(n-i);
              A[i] = A[randomPos];
              A[randomPos] = tmp;
          }
          Arrays.sort(A);
       }
       static void sort(long[] A){
  	        int n = A.length;
  	        Random rnd = new Random();
  	        for(int i=0; i<n; ++i){
  	            long tmp = A[i];
  	            int randomPos = i + rnd.nextInt(n-i);
  	            A[i] = A[randomPos];
  	            A[randomPos] = tmp;
  	        }
  	        Arrays.sort(A);
  	     }
    static String sort(String s) {
   	 Character ch[]=new Character[s.length()];
   	 for(int i=0;i<s.length();i++) {
   		 ch[i]=s.charAt(i);
   	 }
   	 Arrays.sort(ch);
   	 StringBuffer st=new StringBuffer("");
 for(int i=0;i<s.length();i++) {
	 st.append(ch[i]);
 }
 return st.toString();
}
static HashMap<Integer,Integer> hash(int A[]){
  HashMap<Integer,Integer> map=new HashMap<Integer, Integer>();
  for(int i : A) {
	  if(map.containsKey(i)) {
		  map.put(i, map.get(i)+1);
	  }
	  else {
		  map.put(i, 1);
	  }
  }
  return map;
}
static HashMap<Long,Integer> hash(long A[]){
	  HashMap<Long,Integer> map=new HashMap<Long, Integer>();
	  for(long i : A) {
		  if(map.containsKey(i)) {
			  map.put(i, map.get(i)+1);
		  }
		  else {
			  map.put(i, 1);
		  }
	  }
	  return map;
	}
static TreeMap<Integer,Integer> tree(int A[]){
  TreeMap<Integer,Integer> map=new TreeMap<Integer, Integer>();
  for(int i : A) {
	  if(map.containsKey(i)) {
		  map.put(i, map.get(i)+1);
	  }
	  else {
		  map.put(i, 1);
	  }
  }
  return map;
}
static TreeMap<Long,Integer> tree(long A[]){
	  TreeMap<Long,Integer> map=new TreeMap<Long, Integer>();
	  for(long i : A) {
		  if(map.containsKey(i)) {
			  map.put(i, map.get(i)+1);
		  }
		  else {
			  map.put(i, 1);
		  }
	  }
	  return map;
	}
static void primefact(int n) {
	  for(int i=2;i*i<=n;i++) {
		  if(n%i==0) {
			  int cnt=0;
			  while(n%i==0) {
				  cnt++;
				  n/=i;
			  }
			  System.out.println(i+"^"+cnt);
			  
		  }
	  }
	  if(n>1) {
		  System.out.println(n+"^ 1");
	  }
}
   static boolean prime(int n) 
    { 
        if (n <= 1) 
            return false; 
        if (n <= 3) 
            return true; 
        if (n % 2 == 0 || n % 3 == 0) 
            return false; 
        double sq=Math.sqrt(n);
  
        for (int i = 5; i <= sq; i = i + 6) 
            if (n % i == 0 || n % (i + 2) == 0) 
                return false; 
        return true; 
    } 
   static boolean prime(long n) 
    { 
        if (n <= 1) 
            return false; 
        if (n <= 3) 
            return true; 
        if (n % 2 == 0 || n % 3 == 0) 
            return false; 
        double sq=Math.sqrt(n);
  
        for (int i = 5; i <= sq; i = i + 6) 
            if (n % i == 0 || n % (i + 2) == 0) 
                return false; 
        return true; 
    } 
   static long power(long x, long y, long p)
   {

       long res = 1;
       x = x % p;

       while (y > 0) {

           if (y % 2 == 1)
               res = (res * x) % p;

           y = y >> 1; 
           x = (x * x) % p;
       }

       return res;
   }

   static long modInverse(long n, long p)
   {
       return power(n, p - 2, p);
   }
   static int gcd(int a, int b) 
   { 
       if (a == 0) 
           return b; 
       return gcd(b % a, a); 
   } 
   static long gcd(long a, long b) 
   { 
       if (a == 0) 
           return b; 
       return gcd(b % a, a); 
   } 
  
      
  static class FastReader 
  { 
      BufferedReader br; 
      StringTokenizer st; 

      public FastReader() 
      { 
          br = new BufferedReader(new
                   InputStreamReader(System.in)); 
      } 

      String next() 
      { 
          while (st == null || !st.hasMoreElements()) 
          { 
              try
              { 
                  st = new StringTokenizer(br.readLine()); 
              } 
              catch (IOException  e) 
              { 
                  e.printStackTrace(); 
              } 
          } 
          return st.nextToken(); 
      } 

      int nextInt() 
      { 
          return Integer.parseInt(next()); 
      } 

      long nextLong() 
      { 
          return Long.parseLong(next()); 
      } 

      double nextDouble() 
      { 
          return Double.parseDouble(next()); 
      } 

      String nextLine() 
      { 
          String str = ""; 
              try
              { 
                  str = br.readLine(); 
              } 
              catch (IOException e) 
              { 
                  e.printStackTrace(); 
              } 
              return str; 
          } 
      } 
  } 



