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


public class D
{
	BufferedReader in;
	PrintStream out;
	StringTokenizer tok;
	public D() throws NumberFormatException, IOException
	{
		in = new BufferedReader(new InputStreamReader(System.in));
		//in = new BufferedReader(new FileReader("in.txt"));
		out = System.out;
		run();
	}
	class Q implements Comparable<Q>
	{
		int l,r;
		int answer;
		int pos;
		public Q(int l, int r, int pos)
		{
			this.l = l; this.r = r;
			this.pos = pos;
		}
		@Override
		public int compareTo(Q q) 
		{
			if(l != q.l) return l-q.l;
			else return r-q.r;
		}
		
	}
	int[] t;
	int sum (int r) 
	{
		if(r==0) return 0;
		int result = 0; 
		for (; r > 0; r-= r&-r ) 
			result += t [r]; 
		return result;
	} 
	void inc (int i, int delta) 
	{
		if(i==0)return;
		for (; i < 100001; i += i &-i) 
			t [i] += delta;
	} 
	int sum (int l, int r) 
	{
		return sum (r) - sum (l-1);
	}
	void run() throws NumberFormatException, IOException
	{
		int n = nextInt(); 
		int m = nextInt();
		t = new int[100001];
		TreeMap<Integer,List<Integer>> pos = new TreeMap<Integer,List<Integer>>();
		
		int[] num = new int[n];
		int[] nextx = new int[n];
		Arrays.fill(nextx, -1);
		int[] next = new int[n];
		Arrays.fill(next, -1);
		for(int i = 0; i < n; i++)
		{
			num[i] = nextInt();
			if(pos.containsKey(num[i]))
				pos.get(num[i]).add(i);
			else
			{
				List<Integer> l=  new ArrayList<Integer>();
				l.add(i);
				pos.put(num[i], l);
			}
		}
		//set nextx and next and compute first state
		for(int i:pos.keySet())
		{
			List<Integer> p = pos.get(i);
			for(int j = 0; j <= p.size()-i; j++)
				nextx[p.get(j)]=p.get(j+i-1);
			for(int j = 0; j < p.size()-1; j++)
				next[p.get(j)]=p.get(j+1);
			if(p.size()>=i)
			{
				inc(p.get(i-1)+1,1);
				if(p.size()>i)
					inc(p.get(i)+1,-1);
			}
		}
		//querys
		Q[] q = new Q[m];
		for(int i = 0; i < m; i++)
		{
			q[i] = new Q(nextInt()-1,nextInt()-1,i);
		}
		Arrays.sort(q);
		int current = 0;
		
		while(current < m && q[current].l==0)
		{
			q[current].answer = sum(1,q[current].r+1);
			current++;
		}
		for(int i = 1; i < n; i++)
		{
			//update
			if(nextx[i-1]!= -1)
			{
				inc(nextx[i-1]+1,-1);
				if(next[nextx[i-1]]!=-1)
				{
					inc(next[nextx[i-1]]+1,2);
					if(next[next[nextx[i-1]]]!=-1)
						inc(next[next[nextx[i-1]]],-1);
				}
			}
			//compute answers
			while(current < m && q[current].l==i)
			{
				q[current].answer = sum(i+1,q[current].r+1);
				current++;
			}
		}
		int[] sol = new int[m];
		for(int i = 0; i < m; i++)
			sol[q[i].pos] = q[i].answer;
		for(int i = 0; i < m; i++)
			out.println(sol[i]);
	}
	public static void main(String[] args) throws NumberFormatException, IOException 
	{
		new D();
	}
	String nextToken() throws IOException
	{
		if(tok ==null || !tok.hasMoreTokens()) tok = new StringTokenizer(in.readLine());
		return tok.nextToken();
	}
	int nextInt() throws NumberFormatException, IOException
	{
		return Integer.parseInt(nextToken());
	}
	long nextLong() throws NumberFormatException, IOException
	{
		return Long.parseLong(nextToken());
	}
	double nextDouble() throws NumberFormatException, IOException
	{
		return Double.parseDouble(nextToken());
	}
}
