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.util.*;

public class ElephantArray implements Runnable {
  public void run() {
    try {
      Scanner in = new Scanner(System.in);
      //BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int n = in.nextInt();
      int m = in.nextInt();
      int[] a = new int[n];
      int[] b = new int[n + 1];
      for (int i = 0; i < n; i++) {
        a[i] = in.nextInt();
        b[i] = a[i];
      }
      b[n] = Integer.MAX_VALUE;
      Arrays.sort(b);
      int k = -1;
      int num = 0;
      HashSet<Integer> p = new HashSet<Integer>();
      for  (int i = 0; i <= n; i++) {
        if (b[i] != k) {
          if (k != -1 && num >= k) {
            p.add(k);
          }
          num = 1;
          k = b[i];
        } else {
          num++;
        }
      }
      int[] l = new int[m];
      int[] r = new int[m];
      for (int i = 0; i < m; i++) {
        l[i] = in.nextInt();
        r[i] = in.nextInt();
      }
      int[] res = new int[m];
      for (Integer c: p) {
        int[] nn = new int[n + 1];
        nn[0] = 0;
        for (int i = 0; i < n; i++) {
          nn[i + 1] = nn[i];
          if (a[i] == c) {
            nn[i + 1]++;
          }
        }
        for (int i = 0; i < m; i++) {
          if (nn[r[i]] - nn[l[i] - 1] == c) {
            res[i]++;
          }
        }
      }
      for (int i = 0; i < m; i++) {
        System.out.println(res[i]);
      }
    } catch (Exception e) {
      throw new RuntimeException(e);
    }
  }

  public static void main(String[] args) {
    new Thread(new ElephantArray()).start();
  }
}
