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.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class P221D
{
	static int size;
	public static void main(String[] args)
	{		
		FastScanner scan = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);
		int n = scan.nextInt();
		int q = scan.nextInt();
		size = (int)Math.sqrt(n);
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = scan.nextInt();
		Query[] queries = new Query[q];
		for (int i = 0; i < q; i++)
			queries[i] = new Query(i, scan.nextInt()-1, scan.nextInt()-1);
		Arrays.sort(queries);
		int left = 0, right = -1;
		int cnt = 0;
		int[] freq = new int[100001];
		int[] ans = new int[q];
		for (int i = 0; i < q; i++)
		{
			int a = queries[i].a, b = queries[i].b;
			while (left > a)
			{
				left--;
				if (arr[left] >= freq.length)
					continue;
				if (freq[arr[left]] == arr[left])
					cnt--;
				freq[arr[left]]++;
				if (freq[arr[left]] == arr[left])
					cnt++;
			}
			while (right < b)
			{
				right++;
				if (arr[right] >= freq.length)
					continue;
				if (freq[arr[right]] == arr[right])
					cnt--;
				freq[arr[right]]++;
				if (freq[arr[right]] == arr[right])
					cnt++;
			}
			while (left < a)
			{
				if (arr[left] >= freq.length)
				{
					left++;
					continue;
				}
				if (freq[arr[left]] == arr[left])
					cnt--;
				freq[arr[left]]--;
				if (freq[arr[left]] == arr[left])
					cnt++;
				left++;
			}
			while (right > b)
			{
				if (arr[right] >= freq.length)
				{
					right--;
					continue;
				}
				if (freq[arr[right]] == arr[right])
					cnt--;
				freq[arr[right]]--;
				if (freq[arr[right]] == arr[right])
					cnt++;
				right--;
			}
			ans[queries[i].ind] = cnt;
		}
		for (int i = 0; i < q; i++)
			pw.println(ans[i]);
		pw.flush();
	}
	static class Query implements Comparable<Query>
	{
		int a, b, ind;
		Query(int i, int x, int y)
		{
			ind = i;
			a = x;
			b = y;
		}
		public int compareTo(Query q)
		{
			if (a/size == q.a/size)
				return b-q.b;
			return a/size - q.a/size;
		}
	}
	static class FastScanner
	{
		BufferedReader br;
		StringTokenizer st;

		public FastScanner()
		{
			try
			{
				br = new BufferedReader(new InputStreamReader(System.in));
				st = new StringTokenizer(br.readLine());
			} catch (Exception e)
			{
				e.printStackTrace();
			}
		}

		public String next()
		{
			if (st.hasMoreTokens())
				return st.nextToken();
			try
			{
				st = new StringTokenizer(br.readLine());
			} catch (Exception e)
			{
				e.printStackTrace();
			}
			return st.nextToken();
		}

		public int nextInt()
		{
			return Integer.parseInt(next());
		}

		public long nextLong()
		{
			return Long.parseLong(next());
		}

		public String nextLine()
		{
			String line = "";
			try
			{
				line = br.readLine();
			} catch (Exception e)
			{
				e.printStackTrace();
			}
			return line;
		}
	}
}
