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.io.*;

public class Main {
	
	static StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	
	static long[] arr=new long[100009];
	
	static long[] f=new long[100009];
	
	static HashMap<Long,Integer> map=new HashMap<Long,Integer>();
	
	static long[] tree=new long[100009];
	
	static int[][] ask=new int[100009][3];
	
	static long[] ans=new long[100009];
	
	static ArrayList<ArrayList<Integer>> queue=new ArrayList<ArrayList<Integer>>();
	
	static int[] p=new int[100008];
	
	static int n,m,mm;
	
	static Comparator<int[]> comparator=new Comparator<int[]>()
			{
				public int compare(int[] o1, int[] o2) 
				{
				   if(o1[1]<o2[1]) return -1;
				   
				   if(o1[1]>o2[1]) return 1;
				   
					return 0;
				}
		
			};
			
	public static void prepare()throws IOException
	{
		
		for(int i=1;i<=n;i++)
		{
			if(f[i]!=f[i-1])
			{
				 mm++; 
				
			     map.put(f[i],mm);
			}
		}
		for(int i=0;i<=mm;i++)
		{
			ArrayList<Integer> kk=new ArrayList<Integer>();
			
			kk.add(0);
			
			queue.add(i,kk);
		}
		
		for(int i=1;i<=m;i++)
		{
			in.nextToken(); ask[i][0]=(int)in.nval;
			
			in.nextToken(); ask[i][1]=(int)in.nval;
			
			ask[i][2]=i;
		}
		
		Arrays.sort(ask,1,m+1,comparator);
		
	}
	
	public static void update(int x,int k)
	{
		while(x<=n)
		{
			tree[x]+=(long)k;
			
			x+=x&(-x);
			
		}
	}
	
	public static long query(int x)
	{
		long ans=0l;
		
		while(x>0)
		{
			ans+=(long)tree[x];
			
			x-=x&(-x);
		}
		return ans;
	}
	
	public static void work()
	{
		int order=1;
		
		for(int i=1;i<=n;i++)
		{
			
			int op=map.get(arr[i]);
			
			p[op]++;
			
			ArrayList<Integer> kk=queue.get(op); kk.add(i);
			
			if(p[op]>=arr[i])
			{
				update(kk.get(p[op]-(int)arr[i])+1,1);
				
				update(kk.get(p[op]-(int)arr[i]+1)+1,-1);
				
				if(p[op]>arr[i])
				{
					update(kk.get(p[op]-(int)arr[i]-1)+1,-1);
					
					update(kk.get(p[op]-(int)arr[i])+1,1);
				}
			}
			while(order<=m&&ask[order][1]==i)
			{
				ans[ask[order][2]]+=query(ask[order][0]);
				
				order++;
			}
		}
		for(int i=1;i<=m;i++)
		{
			System.out.println(ans[i]);
		}
	}
	
	public static void main(String[] args)throws IOException
	{
		in.nextToken(); n=(int)in.nval;
		
		in.nextToken(); m=(int)in.nval;
		
		for(int i=1;i<=n;i++)
		{
			in.nextToken();
			
			arr[i]=(long)in.nval; f[i]=arr[i];
		}
		Arrays.sort(f,1,n+1);
		
		prepare();
		
		work();
	}

}

	     		 		 	  					 			 	 	  	