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.io.OutputStreamWriter;
import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.StringTokenizer;
import java.io.InputStream;

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

class TaskB {
	public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.nextInt(), m = in.nextInt();
        int[] a = IOUtils.getIntArray(in, n, 1);
        int[] left = new int[m], right = new int[m], res = new int[m];
        for (int i = 0; i < m; i++) {
            left[i] = in.nextInt();
            right[i] = in.nextInt();
        }

        int[] count = new int[n + 1];
        for (int i = 1; i <= n; ++i)
            if (a[i] <= n) ++count[a[i]];

        for (int x = 1; x <= n; ++x)
            if (count[x] >= x) {
                int[] d = new int[n + 1];
                for (int i = 1; i <= n; ++i)
                    d[i] = d[i - 1] + (a[i] == x ? 1 : 0);
                for (int i = 0; i < m; ++i)
                    if (d[right[i]] - d[left[i] - 1] == x) ++res[i];
            }

        for (int i = 0; i < m; ++i)
            out.printLn(res[i]);
	}
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer tokenizer;

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

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

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

    }

class OutputWriter {
    private PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void print(Object...objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0)
                writer.print(' ');
            writer.print(objects[i]);
        }
    }

    public void printLn(Object...objects) {
        print(objects);
        writer.println();
    }

    public void close() {
        writer.close();
    }
}

class IOUtils {

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

    }

