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.List;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author gnosis
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskD solver = new TaskD();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskD {
  static final int MAXN = 100001;
  int nodeCnt;
  int queryCnt;
  int[] arr;
//  int[] dp;
  ArrayList<List<Node>> queryMap; // queryMap[x]: end with x indices
  ArrayList<List<Integer>> pVector;
  SegmentTreeOne stree;
  int[] answer;

  class Node {
    public int left, queryNo;
    Node(int l, int no){left = l; queryNo = no;}
  }

	public void solve(int testNumber, InputReader in, PrintWriter out) {
    nodeCnt = in.nextInt();
    queryCnt = in.nextInt();
    arr = new int[nodeCnt];
    answer = new int[queryCnt];
    stree = new SegmentTreeOne(0, nodeCnt - 1);

    queryMap = new ArrayList<List<Node>>();
    pVector  = new ArrayList<List<Integer>>();
    for(int i = 0; i <= MAXN; ++i) {
      queryMap.add(new ArrayList<Node>());
      pVector.add(new ArrayList<Integer>());
    }

    for(int i = 0; i < nodeCnt; ++i) {
      arr[i] = in.nextInt();
    }

    for(int i = 0; i < queryCnt; ++i) {
      int left = in.nextInt();
      int right = in.nextInt();
      Node node = new Node(left - 1, i);
      queryMap.get(right - 1).add(node);
    }

    for(int i = 0; i < nodeCnt; ++i) {
      int x = arr[i];
      int index ;
      if( x <= nodeCnt ) {
        pVector.get(x).add(i);
        int size = pVector.get(x).size();
        if( size >= x ) {
          index = pVector.get(x).get(size - x);
          stree.update(index, 1);
        }
        if( size > x ) {
          index = pVector.get(x).get(size - x - 1);
          stree.update(index, -2);
        }
        if( size > x + 1) {
          index = pVector.get(x).get(size - x - 2);
          stree.update(index, 1);
        }
      }

      for(int j = 0; j < queryMap.get(i).size(); ++j) {
        Node t = queryMap.get(i).get(j);
        int ret = stree.query(t.left, i);
        answer[ t.queryNo ] = ret;
      }
    }

    for(int a : answer)
      out.println(a);
  }
}

class SegmentTreeOne  {
  int[] sum;
  final int MAXN;
  int left, right;

  public SegmentTreeOne(int l, int r) {
    MAXN = (r - l) + 2;
    sum = new int[4 * MAXN];
    this.left = l;
    this.right = r;
    build(l, r, 1);
  }

  public void build(int l, int r, int no) {
    if(l == r) {
      sum[l] = 0;
      return;
    }
    int mid = (l + r)>>1;
    build(l, mid, no<<1);
    build(mid + 1, r, no<<1|1);
  }

  public void update(int index, int value) {
    update(left, right, 1, index, value);
  }

  public void update(int l, int r, int no, int index, int value) {
    if(index < l || index > r)
      return;

    if(l == r) {
      sum[no] += value;
    }
    else {
      int mid = (l + r)>>1;
      update(l, mid, no<<1, index, value);
      update(mid+1, r, no<<1|1, index, value);
      pushUp(no);
    }
  }

  public int query(int qa, int qb) {
    return query(left, right, 1, qa, qb);
  }

  public int query(int l, int r, int no, int qa, int qb) {
    if(r < qa || l > qb)
      return 0;
    int ans = 0;
    int mid = (l + r)>>1;
    if(qa <=l && r <= qb)
      return sum[no];
    else {
      ans += query(l, mid, no<<1, qa, qb);
      ans += query(mid+1, r, no<<1|1, qa, qb);
    }
    return ans;
  }

  private void pushUp(int no) {
    sum[no] = sum[no<<1] + sum[no<<1|1];
  }

}

class InputReader {
  private BufferedReader reader;
  private StringTokenizer tokenizer;

  public InputReader(InputStream stream) {
    reader = new BufferedReader(new InputStreamReader(stream));
    tokenizer = null;
  }

  public String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new StringTokenizer(reader.readLine());
      } catch (IOException e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

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

}

