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 Solution {
    int[] f = new int[100100];
    int ans; 
    void add(int x)
    {
        if(x>=100100)return;
        if(f[x] == x)ans--;
        f[x]++;
        if(f[x] == x)ans++;
    } 
    void remove(int x)
    {
           if(x>=100100)return;
     
        if(f[x] != 0)
        {
            if(f[x] == x)
                ans--;
            f[x]--;
            if(f[x] == x)ans++;
            
        }
    }       
    void  start()
    {
  Scanner input = new Scanner(System.in);
    int[] arr;
   
        int n = input.nextInt();
         int q = input.nextInt();
         int[][] query = new int[q][3];
         int[] ans_arr = new int[q];
         arr = new int[n+1];
         ans  = 0;
         for(int i=1;i<=n;i++)arr[i] = input.nextInt();
         
         int block_size = (int)(Math.sqrt(n));
         
         for(int i=0;i<q;i++)
         {
             query[i][0] = input.nextInt();
             query[i][1] = input.nextInt();
             query[i][2] = i;
         }
         
      Arrays.sort(query,new Comparator<int[]>() {
             @Override
             public int compare(int[] o1, int[] o2) {
                 if(o1[0]/block_size != o2[0]/block_size)
                 return o1[0] - o2[0];
                 
                 return o1[1] - o2[1];
             }
         } );
    
         int l = 1;
         int r = n;
         int index = l;
         while(index<=r)
         {
              add(arr[index]);
              index++;
         }
         for(int i=0;i<q;i++)
         {
             int L = query[i][0];
             int R = query[i][1];
             while(r<R)
                 add(arr[++r]);
             while(r>R)
                 remove(arr[r--]);
           while(l>L)
                 add(arr[--l]);
             while(l<L)
                 remove(arr[l++]);
             
    ans_arr[query[i][2]] = ans;
    
         }
         for(int i=0;i<q;i++)
             System.out.println(ans_arr[i]);
             }


public static void main(String[] args) {
    Solution s = new Solution();
    s.start();
   
}

}