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
/*
 *created by Kraken on 05-05-2020 at 04:07
 */
//package com.kraken.cf.practice;

import java.util.*;
import java.io.*;

public class B220 {
  private static final int MAXN = (int) 1e5;

  private static Query[] queries;
  private static int n, m, BLOCK_SIZE, ml, mr, ans;
  private static long[] x, res;
  private static long[] cnt;

  private static class Query {
    int l, r, idx;

    public Query(int l, int r, int idx) {
      this.l = l;
      this.r = r;
      this.idx = idx;
    }

    @Override
    public String toString() {
      return "Query{" +
        "l=" + l +
        ", r=" + r +
        ", idx=" + idx +
        '}';
    }
  }

  private static void add(int idx) {
    if (x[idx] > MAXN) return;
    if (cnt[(int) x[idx]] == x[idx]) ans--;
    cnt[(int) x[idx]]++;
    if (cnt[(int) x[idx]] == x[idx]) ans++;
  }

  private static void remove(int idx) {
    if (x[idx] > MAXN) return;
    if (cnt[(int) x[idx]] == x[idx]) ans--;
    cnt[(int) x[idx]]--;
    if (cnt[(int) x[idx]] == x[idx]) ans++;
  }

  public static void main(String[] args) {
    FastReader sc = new FastReader();
    n = sc.nextInt(); m = sc.nextInt();
    BLOCK_SIZE = (int) Math.sqrt(n);
    x = new long[n];
    res = new long[m];
    queries = new Query[m];
    cnt = new long[100001];
    for (int i = 0; i < n; i++) x[i] = sc.nextLong();
    for (int i = 0; i < m; i++) {
      int l = sc.nextInt() - 1, r = sc.nextInt() - 1;
      queries[i] = new Query(l, r, i);
    }
    Arrays.sort(queries, (
      (o1, o2) -> {
        if (o1.l / BLOCK_SIZE == o2.l / BLOCK_SIZE) return o1.r - o2.r;
        else return o1.l / BLOCK_SIZE - o2.l / BLOCK_SIZE;
      })
    );
    ml = 0; mr = -1; ans = 0;
    for (Query q : queries) {
      while (mr > q.r) {
        remove(mr);
        mr--;
      }
      while (mr < q.r) {
        mr++;
        add(mr);
      }
      while (ml > q.l) {
        ml--;
        add(ml);
      }
      while (ml < q.l) {
        remove(ml);
        ml++;
      }
      res[q.idx] = ans;
    }
    StringBuilder sb = new StringBuilder();
    for (long i : res) sb.append(i + "\n");
    System.out.print(sb);
  }

  static class FastReader {

    BufferedReader br;

    StringTokenizer st;

    public FastReader() {
      br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
      while (st == null || !st.hasMoreElements()) {
        try {
          st = new StringTokenizer(br.readLine());
        }
        catch (IOException e) {
          e.printStackTrace();
        }
      }
      return st.nextToken();
    }

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

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

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

    String nextLine() {
      String str = "";
      try {
        str = br.readLine();
      }
      catch (IOException e) {
        e.printStackTrace();
      }
      return str;
    }
  }
}
