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
input = raw_input
range = xrange
import math
from collections import defaultdict

class Query:
	def __init__(self, l, r, index):
		self.l = l - 1
		self.r = r - 1
		self.index = index

def solve():
	n, m = map(int, input().split())
	a = list(map(int, input().split()))
	for i in range(n):
		a[i] = min(a[i], n + 5)
	queries = []
	for i in range(m):
		l, r = map(int, input().split())
		queries.append(Query(l, r, i))
	SQRT = int(math.sqrt(n))
	def compare(f, s):
		f_block = f.l / SQRT
		s_block = s.l / SQRT
		if f_block != s_block: return f_block - s_block
		return f.r - s.r 
	queries.sort(cmp = compare) 
	count = [0] * (n + 10)
	ans = 0
	l = 0
	r = -1
	for q in queries:
		while r < q.r:
			if count[a[r + 1]] == a[r + 1]: ans -= 1
			count[a[r + 1]] += 1 
			if count[a[r + 1]] == a[r + 1]: ans += 1
			r += 1
		while r > q.r:
			if count[a[r]] == a[r]: ans -= 1
			count[a[r]] -= 1
			if count[a[r]] == a[r]: ans += 1
			r -= 1
		while l < q.l:
			if count[a[l]] == a[l]: ans -= 1
			count[a[l]] -= 1
			if count[a[l]] == a[l]: ans += 1
			l += 1
		while l > q.l:
			if count[a[l - 1]] == a[l - 1]: ans -= 1
			count[a[l - 1]] += 1
			if count[a[l - 1]] == a[l - 1]: ans += 1
			l -= 1
		q.ans = ans
	queries.sort(key = lambda q : q.index)
	print "\n".join(map(str, [q.ans for q in queries]))

solve()