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.*;
import java.io.*;
public class A
{
      public static void main(String ar[]) throws Exception
      {
            BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
            String s1[]=br.readLine().split(" ");
            int n=Integer.parseInt(s1[0]);
            int m=Integer.parseInt(s1[1]);
            String s2[]=br.readLine().split(" ");
            int a[]=new int[n];
            for(int i=0;i<n;i++)
             a[i]=Integer.parseInt(s2[i]);
            
            HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>();
            ArrayList<Integer> al=new ArrayList<Integer>();
            for(int i=0;i<n;i++)
            {
                  if(hm.containsKey(a[i]))
                   hm.put(a[i],1+hm.get(a[i]));
                  else
                   hm.put(a[i],1);
                  if(hm.get(a[i])==a[i])
                   al.add(a[i]);
            }
            
            int nn=al.size();
            int b[]=new int[nn];
            for(int i=0;i<nn;i++)
             b[i]=al.get(i);
            Arrays.sort(b);
            int c[][]=new int[n+1][nn];
            for(int i=0;i<n;i++)
            {
                  int v=Arrays.binarySearch(b,a[i]);
                  if(v>=0)
                   c[i+1][v]++;
                  for(int j=0;j<nn;j++)
                   c[i+1][j]+=c[i][j];
            }
            
            for(int i=0;i<m;i++)
            {
                  String s3[]=br.readLine().split(" ");  int t=0;
                  int l=Integer.parseInt(s3[0]);
                  int r=Integer.parseInt(s3[1]);
                  for(int j=0;j<nn;j++)
                  {
                        if(c[r][j]-c[l-1][j]==b[j])
                         t++;
                  }
                  System.out.println(t);
            }
      }
}