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

public class Main
	{
	public static void main(String args[]) throws IOException
		{
		Scanner c=new Scanner(System.in);
		int N=c.nextInt();
		int M=c.nextInt();
		int A[]=new int[N];
		for(int i=0;i<N;i++)
			A[i]=c.nextInt();
		HashMap<Integer,Integer> map=arrayOccurenceCount(A);
		ArrayList<Integer> important=new ArrayList<Integer>();
		for(int a:map.keySet())
			{
			if(map.get(a)>=a)
				important.add(a);
			}
		int L[]=new int[M];
		int R[]=new int[M];
		int res[]=new int[M];
		for(int i=0;i<M;i++)
			{
			L[i]=c.nextInt()-1;
			R[i]=c.nextInt()-1;
			}
		for(int val:important)
			{
			int occ[]=new int[N];
			if(A[0]==val)
				occ[0]=1;
			for(int i=1;i<N;i++)
				occ[i]=occ[i-1]+(A[i]==val?1:0);
			for(int i=0;i<M;i++)
				{
				if(L[i]==0&&occ[R[i]]==val)
					res[i]++;
				else if(L[i]>0&&(occ[R[i]]-occ[L[i]-1]==val))
					res[i]++;
				}
			}
		for(int i=0;i<M;i++)
			System.out.println(res[i]);
		}

	/*Returns a HashMap which maps integers to the number of times they
	 * occur in the array A.
	 */
	private static HashMap<Integer, Integer> arrayOccurenceCount(int[] A)
		{
		HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
		for(int i=0;i<A.length;i++)
			{
			if(map.containsKey(A[i]))
				map.put(A[i],map.get(A[i])+1);
			else
				map.put(A[i],1);
			}
		return map;
		}
	
	}

//must declare new classes here