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.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class Main
{
	public static void main(String[] args) {
		new Thread(null, new Runnable() {
			public void run() {
                solve();
            }
        }, "1", 1 << 26).start();
	}
	static void solve () {
		FastReader fr =new FastReader();	PrintWriter op =new PrintWriter(System.out);
 
 		int n =fr.nextInt() ,m =fr.nextInt() ,position[][] =new int[n+1][2] ,i ,j ,k =-1 ,left ,right ,ctr ;

 		int eligible[][] =new int[446][n+2] ;

 		for (i =1 ; i<=n ; ++i) {
 			position[i][0] =fr.nextInt() ;

 			position[i][1] =i ;
 		}

 		sort (position , 1 , n) ;

 		for (i =1 ; i<=n ; ++i) {
 			j =i ;

 			while (i+1<=n && position[i+1][0]==position[j][0])
 				++i ;

 			if (i-j+1 < position[j][0])
 				continue ;

 			++k ;

 			for (int itr =j ; itr<=i ; ++itr)
 				eligible[k][position[itr][1]] =1 ;

 			eligible[k][n+1] =position[j][0] ;
 		}

 		for (i =0 ; i<=k ; ++i) {
 			for (j =1 ; j<=n ; ++j)
 				eligible[i][j] += eligible[i][j-1] ;
 		}

 		while (m-- > 0) {
 			left =fr.nextInt() ;	right =fr.nextInt() ;	ctr =0 ;

 			for (i =0 ; i<=k ; ++i) {
 				j =eligible[i][right] - eligible[i][left-1] ;

 				if (j==eligible[i][n+1])
 					++ctr ;
 			}

 			op.println(ctr) ;
 		}

		op.flush();	op.close();
	}
	static void sort(int[][] arr , int l , int u) {
		int m ;
 
		if(l < u){
			m =(l + u)/2 ;
 
			sort(arr , l , m);	sort(arr , m + 1 , u);
 
			merge(arr , l , m , u);
		}
	} 
	static void merge(int[][]arr , int l , int m , int u) {
		int[][] low = new int[m - l + 1][2];
 
		int[][] upr = new int[u - m][2];
 
		int i ,j =0 ,k =0 ;
 
		for(i =l;i<=m;i++){
			low[i - l][0] =arr[i][0];
			low[i - l][1] =arr[i][1];
		}
 
		for(i =m + 1;i<=u;i++){
			upr[i - m - 1][0] =arr[i][0];
			upr[i - m - 1][1] =arr[i][1];
		}
 
		i =l;
 
		while((j < low.length) && (k < upr.length))
		{
			if(low[j][0] < upr[k][0])
			{
				arr[i][0] =low[j][0];
				arr[i++][1] =low[j++][1];
			}
			else
			{
				if(low[j][0] > upr[k][0])
				{
					arr[i][0] =upr[k][0];
					arr[i++][1] =upr[k++][1];
				}
				else
				{
					if(low[j][1] < upr[k][1])
					{
						arr[i][0] =low[j][0];
						arr[i++][1] =low[j++][1];
					}
					else
					{
						arr[i][0] =upr[k][0];
						arr[i++][1] =upr[k++][1];
					}
				}
			}
		}
 
		while(j < low.length)
		{
			arr[i][0] =low[j][0];
			arr[i++][1] =low[j++][1];
		}
 
		while(k < upr.length)
		{
			arr[i][0] =upr[k][0];
			arr[i++][1] =upr[k++][1];
		}
	}
	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();
		}

		String nextLine() {
			String str ="";

			try
			{
				str =br.readLine();
			}
			catch(IOException e)
			{
				e.printStackTrace();
			}

			return str;
		}

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

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