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 javax.management.Query;
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class A {

	static int ans, a[], cnt[];
	static int L, R;

	static void add(int idx)
	{
		int v = a[idx], c = ++cnt[v];
		if(v == 0)
			return;
		if(c == v)
			++ans;
		else if(c == v + 1)
			--ans;
	}

	static void remove(int idx)
	{
		int v = a[idx], c = --cnt[v];
		if(v == 0)
			return;
		if(c == v)
			++ans;
		else if(c == v - 1)
			--ans;
	}

	public static void main(String[] args) throws IOException {

		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		int n = sc.nextInt(), m = sc.nextInt();
		cnt = new int[n + 1];
		a = new int[n];
		for(int i = 0; i < n; ++i)
		{
			a[i] = sc.nextInt();
			if(a[i] > n)
				a[i] = 0;
		}
		Query.s = (int)(Math.sqrt(n));
		Query[] qs = new Query[m];
		for(int i = 0; i < m; ++i)
			qs[i] = new Query(sc.nextInt() - 1, sc.nextInt() - 1, i);
		Arrays.sort(qs);
		int[] res = new int[m];
		int L = 0, R = -1;
		for(Query q: qs)
		{
			while(L < q.left) remove(L++);
			while(L > q.left) add(--L);
			while(R > q.right) remove(R--);
			while(R < q.right) add(++R);
			res[q.idx] = ans;
		}
		for(int x: res)
			out.println(x);
		out.close();
	}

	static class Query implements Comparable<Query>
	{
		static int s;
		int left, right, bLeft, bRight, idx;

		Query(int a, int b, int c)
		{
			left = a;
			right = b;
			bLeft = a / s;
			bRight = b / s;
			idx = c;
		}

		public int compareTo(Query q)
		{
			if(bLeft != q.bLeft)
				return bLeft - q.bLeft;
			return right - q.right;
		}
	}


	static class Scanner
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		public Scanner(String s) throws FileNotFoundException {	br = new BufferedReader(new FileReader(s));}

		public String next() throws IOException
		{
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

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

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

		public String nextLine() throws IOException {return br.readLine();}

		public double nextDouble() throws IOException { return Double.parseDouble(next()); }

		public boolean ready() throws IOException {return br.ready();}
	}
}