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.*;
import java.util.*;
import java.math.*;
import java.text.DecimalFormat;
import java.text.NumberFormat;
 

@SuppressWarnings("unchecked")
public class Main {
      
    int mod = 1000000007;

    public class SegmentTree{

       int n; long[] tree;

       SegmentTree(long[] arr){

          this.n = arr.length; 
          this.tree = new long[2 * n];

          for(int i = n; i < 2 * n; i++) this.tree[i] = arr[i - n];
          for(int i = n - 1; i >= 1; i--) this.tree[i] = Math.max(this.tree[2 * i], this.tree[2 * i + 1]);
       
       }

       public long query(int l, int r){

          long res = Integer.MIN_VALUE;
          l = l + n; 
          r = r + n;

          while(l < r){

              if(l % 2 == 1) res = Math.max(res, tree[l++]); 
              if(r % 2 == 1) res = Math.max(res, tree[--r]);
              l /= 2; r /= 2;
          }

          return res;
       }

       public void update(int idx, long v){
          
          idx += n; this.tree[idx] = v;
          while(idx > 1){
             idx /= 2;
             this.tree[idx] = Math.max(this.tree[2 * idx], this.tree[2 * idx + 1]);
          }
       }


    }

    int n, m, BS;
    int[][] q;
    int[] aa;
    HashMap<Integer, Integer> freq = new HashMap<>();
    int cur = 0;

    public void add(int i){
       if(i < 0 || i >= n) return;
       int num = aa[i];
       int f = freq.getOrDefault(num, 0);
       freq.put(num, freq.getOrDefault(num, 0) + 1);
       if(f == num - 1) cur++;
       else if(f == num) cur--;
    }

    public void remove(int i){
       if(i < 0 || i >= n) return;
       int num = aa[i];
       int f = freq.getOrDefault(num, 0);
       freq.put(num, freq.getOrDefault(num, 0) - 1);
       if(f == num + 1) cur++;
       else if(f == num) cur --;
    }

    public void solve() throws IOException{

         n = in.nextInt();
         m = in.nextInt();
         BS = (int) Math.sqrt(n);
         aa = new int[n];
         for(int i = 0; i < n; i++) aa[i] = in.nextInt();
         q = new int[m][3];

         for(int i = 0; i < m; i++){
            q[i][0] = in.nextInt() - 1;
            q[i][1] = in.nextInt() - 1;
            q[i][2] = i;
         }

         Arrays.sort(q, (e1, e2) -> {
            if(e1[0] / BS != e2[0] / BS){
               return e1[0] / BS - e2[0] / BS;
            }else{
               return e1[1] - e2[1];
            }
         });

         int[] ans = new int[m];

         int l = 0, r = -1;
         for(int i = 0; i < m; i++){

             int L = q[i][0], R = q[i][1];
             
             while(r < R) add(++r);
             while(r > R) remove(r--);
             while(l < L) remove(l++);
             while(l > L) add(--l);
        
             ans[q[i][2]] = cur;
         }

         for(int i = 0; i < m; i++){
            out.println(ans[i]);
         }
            
         return;
    } 




    FastScanner in;
    PrintWriter out;
    
    static class FastScanner {
 
        BufferedReader br;
        StringTokenizer st;
 
        FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
            st = null;
        }
 
        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
 
        String nextLine() throws IOException {
            if (st == null || !st.hasMoreTokens())
                return br.readLine();
            StringBuilder result = new StringBuilder(st.nextToken());
            while (st.hasMoreTokens()) {
                result.append(" ");
                result.append(st.nextToken());
            }
            return result.toString();
        }
 
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
 
        long nextLong() throws IOException {
            return Long.parseLong(next());
        }
 
        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
 
    }
 
    void run() throws IOException {
        in = new FastScanner(System.in);
        out = new PrintWriter(System.out, false);
        solve();
        out.close();
    }
 
    public static void main(String[] args) throws IOException{
        new Main().run();
    }
 
    public void printArr(int[] arr){
        for(int i = 0; i < arr.length; i++){
            out.print(arr[i] + " ");
        }
        out.println();
    }
 
    public long gcd(long a, long b){
        if(a == 0) return b;
        return gcd(b % a, a);
    }

    public boolean isPrime(long num){

        if(num == 0 || num == 1){
            return false;
        }

        for(int i = 2; i * i <= num; i++){
            if(num % i == 0){
                return false;
            }
        }

        return true;
    }

    public class Pair<A, B>{
        public A x; 
        public B y;

        Pair(A x, B y){
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair<?, ?> pair = (Pair<?, ?>) o;
            if (!x.equals(pair.x)) return false;
            return y.equals(pair.y);
        }

        @Override
        public int hashCode() {
            int result = x.hashCode();
            result = 31 * result + y.hashCode();
            return result;
        }

    }

    class Tuple{
        int x; int y; int z;
        Tuple(int ix, int iy, int iz){
            x = ix;
            y = iy;
            z = iz;
        }
    }
}
