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.Arrays;
import java.util.Scanner;

public class practice {

  public static void main(String[] args) {
    try (Scanner sc = new Scanner(System.in)) {
      int t = 1;//sc.nextInt();
      while (t-- > 0) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
          arr[i] = sc.nextInt();
        }
        Pair[] queries = new Pair[m];
        int index = 0;
        while (m-- > 0) {
          queries[index] = new Pair(sc.nextInt() - 1, sc.nextInt() - 1, index);
          index++;
        }
        int sqrt = (int)Math.sqrt(n);
        Arrays.sort(queries, (Pair one, Pair other) -> {
          int block1 = (one.l + sqrt - 1) / sqrt;
          int block2 = (other.l + sqrt - 1) / sqrt;
          if(block1 == block2) return one.r - other.r;
          else return block1 - block2;
        });
        int globalAns = 0;
        int[] answer = new int[queries.length];
        int l = 0;
        int r = -1;
        int MXN = 1000000;
        int[] freq = new int[1000000];
        for (Pair p : queries) {
          while (p.l != l || p.r != r) {
            if (p.r > r) {
              r++;
              if(arr[r] < MXN) {
                int val = arr[r];
                if(freq[val] == val) globalAns--;
                freq[val]++;
                if (freq[val] == val) globalAns++;
              }
            } else if (p.r < r) {
              if(arr[r] < MXN) {
                int val = arr[r];
                if(freq[val] == val) globalAns--;
                freq[val]--;
                if(freq[val] == val) globalAns++;
              }
              r--;
            } else if (p.l < l) {
              l--;
              if(arr[r] < MXN) {
                int val = arr[l];
                if(freq[val] == val) globalAns--;
                freq[val]++;
                if(freq[val] == val) globalAns++;
              }
            } else {
              if(arr[r] < MXN) {
                int val = arr[l];
                if(freq[val] == val) globalAns--;
                freq[val]--;
                if(freq[val] == val) globalAns++;
              }
              l++;
            }

          }
          answer[p.index] = globalAns;
        }
        for (int ans : answer) System.out.println(ans + " ");
      }
    }
  }

  static class Pair {
    int l;
    int r;

    public int getIndex() {
      return index;
    }

    int index;

    public Pair(int l, int r, int index) {
      this.l = l;
      this.r = r;
      this.index = index;
    }
   
  }

}
