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.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeSet;


public class cf220b {
  static int ADD = 0, QUERY = 1;
  public static void main(String[] args) {
    FastIO in = new FastIO(), out = in;
    int n = in.nextInt();
    int m = in.nextInt();
    Queue<Event> q = new PriorityQueue<Event>();
    for(int i=1; i<=n; i++)
      q.add(new Event(in.nextInt(), i, ADD, 0));
    for(int i=0; i<m; i++)
      q.add(new Event(in.nextInt(),in.nextInt(),QUERY,i));
    int[] ans = new int[m];
    BIT bit = new BIT(n+10);
    Map<Integer,ArrayDeque<Integer>> history = new HashMap<Integer,ArrayDeque<Integer>>();
    while(!q.isEmpty()) {
      Event cur = q.poll();
      if(cur.type == ADD) {
        if(!history.containsKey(cur.val))
          history.put(cur.val, new ArrayDeque<Integer>());
        ArrayDeque<Integer> hist = history.get(cur.val);
        hist.add(cur.pos);
        if(hist.size() == cur.val + 2) {
          bit.add(hist.poll(),1);
          bit.add(hist.peek(),-2);
          int tmp = hist.pop();
          bit.add(hist.peek(),1);
          hist.push(tmp);
        }
        else if(hist.size() == cur.val + 1) {
          bit.add(hist.peek(),-2);
          int tmp = hist.pop();
          bit.add(hist.peek(),1);
          hist.push(tmp);
        }
        else if(hist.size() == cur.val) {
          bit.add(hist.peek(),1);
        }
      }
      else {
        ans[cur.id] = bit.sum(cur.val,cur.pos);
      }
    }
    for(int x : ans)
      out.println(x);
    out.close();
  }
  static class BIT {
    int n;
    int[] v;
    public BIT(int N) {
      v = new int[n=N];
    }
    public int sum(int x, int y) {
      return sum(y) - sum(x-1);
    }
    public int sum(int x) {
        return x<0?0:(v[x]+sum((x&(x+1))-1));
    }
    public void add(int p, int x) {
      for(int i=p; i<n; i|=(i+1))
        v[i]+=x;
    }
  }
  static class Event implements Comparable<Event> {
    int val, pos, type, id;
    Event(int a, int b, int c, int d) {
      val = a; pos = b; type = c; id = d;
    }
    public int compareTo(Event e) {
      if(pos != e.pos) return pos - e.pos;
      return type-e.type;
    }
  }
  static class FastIO extends PrintWriter {
    BufferedReader br;
    StringTokenizer st;
    
    public FastIO() {
      this(System.in,System.out);
    }
    public FastIO(InputStream in, OutputStream out) {
      super(new BufferedWriter(new OutputStreamWriter(out)));
      br = new BufferedReader(new InputStreamReader(in));
      scanLine();
    }
    public void scanLine() {
      try {
        st = new StringTokenizer(br.readLine().trim());
      } catch(Exception e) {
        throw new RuntimeException(e.getMessage());
      }
    }
    public int numTokens() {
      if(!st.hasMoreTokens()) {
        scanLine();
        return numTokens();
      }
      return st.countTokens();
    }
    public String next() {
      if(!st.hasMoreTokens()) {
        scanLine();
        return next();
      }
      return st.nextToken();
    }
    public double nextDouble() {
      return Double.parseDouble(next());
    }
    public long nextLong() {
      return Long.parseLong(next());
    }
    public int nextInt() {
      return Integer.parseInt(next());
    }
  }
}