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.OutputStreamWriter;
import java.io.BufferedWriter;
import java.util.Locale;
import java.util.HashMap;
import java.io.OutputStream;
import java.util.RandomAccess;
import java.io.PrintWriter;
import java.util.AbstractList;
import java.io.Writer;
import java.util.List;
import java.util.Map;
import java.io.IOException;
import java.util.Arrays;
import java.math.BigDecimal;
import java.util.InputMismatchException;
import java.util.Set;
import java.math.BigInteger;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Jacob Jiang
 */
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 {

    private int count;
    private int requestCount;
    private int[] a;
    private int[] l;
    private int[] r;
    private int[] answer;

    public void solve(int testNumber, InputReader in, OutputWriter out) {
        count = in.nextInt();
        requestCount = in.nextInt();
        a = in.nextIntArray(count);
        Counter<Integer> counter = new Counter<>();
        for (int i : a) {
            counter.add(i);
        }
        l = new int[requestCount];
        r = new int[requestCount];
        answer = new int[requestCount];
        ArrayUtils.readIntArrays(in, l, r);
        ArrayUtils.decreaseByOne(l, r);
        for (Map.Entry<Integer, Long> entry : counter.entrySet()) {
            if (entry.getKey() <= entry.getValue())
                calc(entry.getKey());
        }
        out.println(StringUtils.mkString(ArrayUtils.asList(answer), "\n"));
    }

    private void calc(int possibleValue) {
        int[] sum = new int[count + 1];
        for (int i = 0; i < count; i++) {
            sum[i + 1] = sum[i] + (a[i] == possibleValue ? 1 : 0);
        }
        for (int i = 0; i < requestCount; i++) {
            if (possibleValue == sum[r[i] + 1] - sum[l[i]]) {
                answer[i]++;
            }
        }
        
    }
}

class InputReader {

    private InputStream stream;
    private byte[] buf = new byte[1 << 16];
    private int curChar;
    private int numChars;

    public InputReader(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++];
    }

    public int nextInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c & 15;
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

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

    public int[] nextIntArray(int count) {
        int[] result = new int[count];
        for (int i = 0; i < count; i++) {
            result[i] = nextInt();
        }
        return result;
    }

    }

class OutputWriter {
    private PrintWriter writer;

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

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

    public void println(String x) {
        writer.println(x);
    }

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

    }

class Counter<T> extends HashMap<T, Long> {

    public void add(T obj) {
        put(obj, get(obj) + 1L);
    }

    public Long get(Object key) {
        return containsKey(key) ? super.get(key) : 0L;
    }
}

class ArrayUtils {

    public static void readIntArrays(InputReader in, int[]... arrays) {
        for (int i = 0; i < arrays[0].length; i++) {
            for (int j = 0; j < arrays.length; j++) {
                arrays[j][i] = in.nextInt();
            }
        }
    }

    public static void decreaseByOne(int[]... arrays) {
        for (int[] array : arrays) {
            for (int i = 0; i < array.length; i++) {
                array[i]--;
            }
        }
    }



    public static List<Integer> asList(int[] array) {
        return new IntList(array);
    }

    private static class IntList extends AbstractList<Integer> implements RandomAccess {

        int[] array;

        private IntList(int[] array) {
            this.array = array;
        }

        public Integer get(int index) {
            return array[index];
        }

        public Integer set(int index, Integer element) {
            int result = array[index];
            array[index] = element;
            return result;
        }

        public int size() {
            return array.length;
        }
    }

    }

class StringUtils {

    public static String mkString(Iterable<?> toPrint, String middle) {
        return mkString(toPrint, "", middle, "");
    }

    public static String mkString(Iterable<?> toPrint, String left, String middle, String right) {
        StringBuilder result = new StringBuilder();
        result.append(left);
        boolean first = true;
        for (Object o : toPrint) {
            if (first) first = false;
            else result.append(middle);
            result.append(o);
        }
        result.append(right);
        return result.toString();
    }

    }

