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
//package codeforces;

import java.io.BufferedReader;
import java.io.Closeable;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class D implements Closeable {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter writer = new PrintWriter(System.out);
    StringTokenizer stringTokenizer;

    D() throws IOException {
//        reader = new BufferedReader(new FileReader("input.txt"));
//        writer = new PrintWriter(new FileWriter("output.txt"));
    }


    String next() throws IOException {
        while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
            stringTokenizer = new StringTokenizer(reader.readLine());
        }
        return stringTokenizer.nextToken();
    }

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

    long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    private double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    int MOD = 1000 * 1000 * 1000 + 7;

    int sum(int a, int b) {
        a += b;
        return a >= MOD ? a - MOD : a;
    }

    int product(int a, int b) {
        return (int) (1l * a * b % MOD);
    }

    @SuppressWarnings("unchecked")
    void solve() throws IOException {
        int n = nextInt();
        int m = nextInt();
        int[] a = new int[n];
        Map<Integer, Integer> countMap = new HashMap<>();
        for(int i = 0; i < n; i++) {
            a[i] = nextInt();
            Integer count = countMap.get(a[i]);
            if(count == null) {
                count = 0;
            }
            countMap.put(a[i], count + 1);
        }
        int[] l = new int[m];
        int[] r = new int[m];
        for(int i = 0; i < m; i++) {
            l[i] = nextInt();
            r[i] = nextInt();
        }
        int[] answer = new int[m];
        int[] q = new int[n + 1];
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            if(entry.getValue() >= entry.getKey()) {
                int x = entry.getKey();
                for(int i = 1; i <= n; i++) {
                    q[i] = q[i - 1] + (a[i - 1] == x ? 1 : 0);
                }
                for(int i = 0; i < m; i++) {
                    if(q[r[i]] - q[l[i] - 1] == x) {
                        answer[i]++;
                    }
                }
            }
        }
        for (int x : answer) {
            writer.println(x);
        }
    }

    public static void main(String[] args) throws IOException, InterruptedException {
        try (D d = new D()) {
            d.solve();
        }
    }

    @Override
    public void close() throws IOException {
        reader.close();
        writer.close();
    }
}