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.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.Comparator;


public class Main {

	static int[] num = null;
	static int[] b = null;
	static Node1[] data = null;
	static Node1[] a = null;
	static Interval1[] query = null;
	static int[] resultmap = null;
	static int result = 0;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		int n, m, l, r, Left, Right, val;
		StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (cin.nextToken() != StreamTokenizer.TT_EOF) {
			n = (int) cin.nval;
			num = new int[n + 1];
			b = new int[n + 1];
			data = new Node1[n+1];
			
			
			cin.nextToken();
			m = (int) cin.nval;
			query = new Interval1[m + 1];
			
			for (int i = 1; i <= n; i++) {
				cin.nextToken();
				val = (int)cin.nval;
				data[i] = new Node1(val, i);
			}
			a = data.clone();
			Arrays.sort(data, 1, n+1, new MyComparatorNode());
			b[data[1].index]=1;
			for(int i=2;i<=n;i++){
				if(data[i].val==data[i-1].val)
					b[data[i].index]=b[data[i-1].index];
				else
					b[data[i].index]=i;
			}
			
			for (int i = 1; i <= m; i++) {
				cin.nextToken();
				l = (int) cin.nval;
				cin.nextToken();
				r = (int) cin.nval;
				query[i] = new Interval1(l, r, i);
			}

			// Initialization
			int blocks = (int) Math.sqrt(n);
			Arrays.sort(query, 1, m + 1, new MyComparator(blocks));
			resultmap = new int[m+1];
			result = 0;
			Left = Right = 1;
			add(1);
			// 莫队处理
			for (int i = 1; i <= m; i++) {
				while (Left < query[i].left) {
					remove(Left);
					Left++;
				}
				while (Left > query[i].left) {
					Left--;
					add(Left);
				}
				while (Right < query[i].right) {
					Right++;
					add(Right);
				}
				while (Right > query[i].right) {
					remove(Right);
					Right--;
				}
				resultmap[query[i].i] = result;
			}
			for(int i=1;i<=m;i++){
				out.println(resultmap[i]);
			}
			out.flush();
		}
		
	}

	private static void add(int x) {
		num[b[x]]++;
		if (num[b[x]] == a[x].val)
			result++;
		if(num[b[x]]==a[x].val+1)
			result--;
	}

	private static void remove(int x) {
		num[b[x]]--;
		if (num[b[x]] == a[x].val - 1)
			result--;
		if (num[b[x]] == a[x].val)
			result++;
	}

}

class Interval1 {
	int left;
	int right;
	int i;
	public Interval1(int left, int right, int i) {
		// TODO Auto-generated constructor stub
		this.left = left;
		this.right = right;
		this.i = i;
	}
}
class Node1{
	int val;
	int index;
	public Node1(int val, int index) {
		// TODO Auto-generated constructor stub
		this.val = val;
		this.index = index;
	}
}
class MyComparator implements Comparator<Interval1> {

	int blocks = 0;

	public MyComparator(int blocks) {
		// TODO Auto-generated constructor stub
		this.blocks = blocks;
	}

	@Override
	public int compare(Interval1 o1, Interval1 o2) {
		// TODO Auto-generated method stub
		if(((o2.left / blocks) == (o1.left / blocks))&&(o1.right==o2.right))
			return 0;
		if ((o2.left / blocks) != (o1.left / blocks)) {
			return o2.left < o1.left ? 1 : -1;
		} else
			return o2.right < o1.right ? 1 : -1;
	}
}
class MyComparatorNode implements Comparator<Node1>{

	@Override
	public int compare(Node1 o1, Node1 o2) {
		// TODO Auto-generated method stub
		if(o1.val==o2.val)
			return 0;
		return o2.val<o1.val?1:-1;
	}
	
}