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.util.*;
import static java.lang.Math.*;
public class ProblemB {
    void run() {
        Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		List<Integer>[] indices = new List[N+1];
		boolean[] good = new boolean[N+1];
		int num_good = 0;
		for (int i = 1; i < N+1; ++i) {
			indices[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < N; ++i) {
			int x = sc.nextInt();
			if (x <= N) {
				indices[x].add(i+1);
				if (indices[x].size() >= x) {
					if (!good[x]) {
						++num_good;
					}
					good[x] = true;
				}
			}
		}

		int[] poss = new int[num_good];
		int i_poss = 0;
		for (int x = 1; x < N+1; ++x) {
			if (good[x]) {
				poss[i_poss] = x;
				++i_poss;
			}
		}

		int[][] ind = new int[N+1][];
		for (int x : poss) {
			int num = indices[x].size();
			int[] row = new int[num];
			for (int i = 0; i < num; ++i) {
				row[i] = indices[x].get(i);
			}
			ind[x] = row;
		}

		long[] queries = new long[M];
		int[] counts = new int[M];

		for (int i = 0; i < M; ++i) {
			long l = sc.nextInt();
			long r = sc.nextInt();
			queries[i] = (l << 40) + (r << 20) + i;
		}
		Arrays.sort(queries);

		for (int x : poss) {
			int[] inx = ind[x];
			int len = inx.length;
			int i = 0;
			for (long q : queries) {
				long mask = (1 << 20) - 1;
				int qi = (int) (q & mask);
				int r = (int) ((q >> 20) & mask);
				int l = (int) ((q >> 40) & mask);
				while (i < len && inx[i] < l) {
					++i;
				}
				int rr = i + x - 1;
				if (rr < len) {
					if (inx[rr] <= r && (rr + 1 >= len || inx[rr+1] > r)) {
						++counts[qi];
					}
				}
			}

		}
		for (int count : counts) {
			p("%d\n", count);
		}
    }

    boolean debug = false;
    void p(String f, Object...params) {
        System.out.printf(f, params);
    }
    void d(Object...params) {
        if (debug) {
            p("DEBUG: %s\n", Arrays.deepToString(params));
        }
    }
    void die() {
        throw new RuntimeException();
    }
    public ProblemB(String[] args) {
        if (args.length > 0 && args[0].equals("debug")) {
            debug = true;
        }
    }
    public static void main(String[] args) {
        new ProblemB(args).run();
    }
}
