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.awt.*;
public class R136_D2_D
{
	public static void main(String args[])
	{
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		int a[]=new int[n];
		for(int i=0;i<n;i++)
			a[i]=sc.nextInt();
		Point[] pnts = new Point[m];
        	int[] res = new int[m];
        	for (int i = 0; i < pnts.length; i++) 
		{
            		pnts[i] = new Point(sc.nextInt() - 1, sc.nextInt() - 1);
        	}
        	HashSet<Integer> set = new HashSet<Integer>();
        	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        	for (int i = 0; i < n; i++) 
		{
            		if (!map.containsKey(a[i])) 
			{
                		map.put(a[i], 1);
            		}
			else 
			{
                		map.put(a[i], map.get(a[i]) + 1);
            		}
            		if (map.get(a[i]) >= a[i] && !set.contains(a[i])) 
			{
                		set.add(a[i]);
                		int comsum[] = new int[n + 1];
                		for (int j = 0; j < n; j++) 
				{
                    			comsum[j + 1] = comsum[j] + (a[j] == a[i] ? 1 : 0);
                		}
                		for (int j = 0; j < pnts.length; j++) 
				{
                    			if (comsum[pnts[j].y + 1] - comsum[pnts[j].x] == a[i]) 
					{
                        			res[j]++;
                    			}
                		}
            		}
        	}
        	for (int i = 0; i < res.length; i++) 
		{
            		System.out.println(res[i]);
        	}
	}
}