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.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author AlexFetisov
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskB solver = new TaskB();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskB {

    public static final int BUBEN = 333;
    private int[] a;
    private int n;
    int[] am;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        n = in.nextInt();
        int countQueries = in.nextInt();
        a = Utils.readIntArray(in, n);
        am = new int[n + 1];
        Query[] queries = new Query[countQueries];
        for (int i = 0; i < countQueries; ++i) {
            queries[i] = new Query(i, in.nextInt()-1, in.nextInt()-1);
        }
        Arrays.sort(queries);
        int prevBlock = -1;
        int curLeft = -1, curRight = -1;
        int res = 0;
        int[] result = new int[countQueries];
        for (int i = 0; i < countQueries; ++i) {
            if (prevBlock != queries[i].block) {
                res = prepareRes(queries[i].left, queries[i].right);
                curLeft = queries[i].left;
                curRight = queries[i].right;
                result[queries[i].id] = res;
                prevBlock = queries[i].block;
            } else {
                res = updateRes(queries[i].left, queries[i].right, curLeft, curRight, res);
                curLeft = queries[i].left;
                curRight = queries[i].right;
                result[queries[i].id] = res;
            }
        }
        for (int i = 0; i < countQueries; ++i) {
            out.println(result[i]);
        }
    }

    private int updateRes(int left, int right, int curLeft, int curRight, int curRes) {
        int res = curRes;
        int deltaLeft = curLeft < left ? 1 : -1;
        int deltaRight = curRight < right ? 1 : -1;
        
        while (left != curLeft) {
            if (curLeft > left) {
                int i = curLeft - 1;
                if (a[i] <= a.length) {
                    if (am[a[i]] == a[i]) {
                        --res;
                    }
                    am[a[i]]++;
                    if (am[a[i]] == a[i]) {
                        ++res;
                    }
                }
                --curLeft;
            } else {
                int i = curLeft;
                if (a[i] <= a.length) {
                    if (am[a[i]] == a[i]) {
                        --res;
                    }
                    am[a[i]]--;
                    if (am[a[i]] == a[i]) {
                        ++res;
                    }
                }
                ++curLeft;
            }
        }

        while (right != curRight) {
            if (curRight < right) {
                int i = curRight + 1;
                if (a[i] <= a.length) {
                    if (am[a[i]] == a[i]) {
                        --res;
                    }
                    am[a[i]]++;
                    if (am[a[i]] == a[i]) {
                        ++res;
                    }
                }
                ++curRight;
            } else {
                int i = curRight;
                if (a[i] <= a.length) {
                    if (am[a[i]] == a[i]) {
                        --res;
                    }
                    am[a[i]]--;
                    if (am[a[i]] == a[i]) {
                        ++res;
                    }
                }
                --curRight;
            }
        }
        return res;
    }

    private int prepareRes(int left, int right) {
        Arrays.fill(am, 0);
        int res = 0;
        for (int i = left; i <= right; ++i) {
            if (a[i] <= a.length) {
                if (am[a[i]] == a[i]) {
                    --res;
                }
                am[a[i]]++;
                if (am[a[i]] == a[i]) {
                    ++res;
                }
            }

        }
        return res;
    }

    class Query implements Comparable<Query> {
        int left, right;
        int block;
        int id;

        public Query(int id, int left, int right) {
            this.id = id;
            this.left = left;
            this.right = right;
            this.block = this.left / BUBEN;
        }

        public int compareTo(Query o) {
            if (block != o.block) {
                return block - o.block;
            }
            if (right != o.right) {
                return right - o.right;
            }
            if (left != o.left) {
                return left - o.left;
            }
            return id - o.id;
        }
    }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer stt;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
    }

    public String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            return null;
        }
    }

    public String nextString() {
        while (stt == null || !stt.hasMoreTokens()) {
            stt = new StringTokenizer(nextLine());
        }
        return stt.nextToken();
    }

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

}

class Utils {
    public static int[] readIntArray(InputReader in, int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = in.nextInt();
        }
        return a;
    }

}

