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.OutputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.ArrayList;
import java.io.InputStream;

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

class TaskB {
	public void solve(int testNumber, StreamInputReader in, PrintWriter out) {
        int N = in.nextInt();
        int M = in.nextInt();
        int[] A = new int[N + 1];
        for(int i = 1; i <= N; i++)
            A[i] = in.nextInt();

        ArrayList<Interval>[] endIn = new ArrayList[N + 1];
        for(int i = 1; i <= N; i++)
            endIn[i] = new ArrayList<Interval>();
        int left, right;
        for(int i = 0; i < M; i++) {
            left = in.nextInt();
            right = in.nextInt();
            endIn[right].add(new Interval(left, right, i));
        }
        int[] ans = new int[M];
        int[] aib = new int[N + 1];

        ArrayList<Integer>[] ap = new ArrayList[N + 1];
        for(int i = 1; i <= N; i++)
            ap[i] = new ArrayList<Integer>();

        for(int i = 1; i <= N; i++) {
            if(A[i] <= N) {
                int t = A[i];
                ap[t].add(i);

                if(ap[t].size() >= t) {
                    update(aib, ap[t].get(ap[t].size() - t), 1);

                    if(ap[t].size() >= t + 1) {
                        update(aib, ap[t].get(ap[t].size() - t - 1), -2);

                        if(ap[t].size() >= t + 2)
                            update(aib, ap[t].get(ap[t].size() - t - 2), 1);
                    }
                }


            }

            for(int j = 0; j < endIn[i].size(); j++)
                ans[endIn[i].get(j).index] += query(aib, i) - query(aib, endIn[i].get(j).left - 1);
        }

        for(int i = 0; i < M; i++)
            out.println(ans[i]);
	}

    private int query(int[] aib, int pos) {
        int ret = 0;
        while(pos > 0) {
            ret += aib[pos];
            pos -= pos & (-pos);
        }
        return ret;
    }

    private void update(int[] aib, int pos, int val) {
        while(pos < aib.length) {
            aib[pos] += val;
            pos += pos & (-pos);
        }
    }

    private class Interval {
        public int left, right, index;

        private Interval(int left, int right, int index) {
            this.left = left;
            this.right = right;
            this.index = index;
        }
    }
}

class StreamInputReader extends InputReader {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar, numChars;

    public StreamInputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    }

abstract class InputReader {

    public abstract int read();

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

    public String nextString() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuffer res = new StringBuffer();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

    private boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    }

