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.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.*;


public class D
{
    BufferedReader in;
    PrintStream out;
    StringTokenizer tok;
    public D() throws NumberFormatException, IOException
    {
        in = new BufferedReader(new InputStreamReader(System.in));
        //in = new BufferedReader(new FileReader("in.txt"));
        out = System.out;
        run();
    }
    class Q implements Comparable<Q>
    {
        int l,r;
        int answer;
        int pos;
        public Q(int l, int r, int pos)
        {
            this.l = l; this.r = r;
            this.pos = pos;
        }
        @Override
        public int compareTo(Q q) 
        {
            if(l != q.l) return l-q.l;
            else return r-q.r;
        }
        
    }
    int[] t;
    int sum (int r) 
    {
        if(r==0) return 0;
        int result = 0; 
        for (; r > 0; r-= r&-r ) 
            result += t [r]; 
        return result;
    } 
    void inc (int i, int delta) 
    {
        if(i==0)return;
        for (; i < 100001; i += i &-i) 
            t [i] += delta;
    } 
    int sum (int l, int r) 
    {
        return sum (r) - sum (l-1);
    }
    void run() throws NumberFormatException, IOException
    {
        int n = nextInt(); 
        int m = nextInt();
        t = new int[100001];
        TreeMap<Integer,List<Integer>> pos = new TreeMap<Integer,List<Integer>>();
        
        int[] num = new int[n];
        int[] nextx = new int[n];
        Arrays.fill(nextx, -1);
        int[] next = new int[n];
        Arrays.fill(next, -1);
        for(int i = 0; i < n; i++)
        {
            num[i] = nextInt();
            if(pos.containsKey(num[i]))
                pos.get(num[i]).add(i);
            else
            {
                List<Integer> l=  new ArrayList<Integer>();
                l.add(i);
                pos.put(num[i], l);
            }
        }
        //set nextx and next and compute first state
        for(int i:pos.keySet())
        {
            List<Integer> p = pos.get(i);
            for(int j = 0; j <= p.size()-i; j++)
                nextx[p.get(j)]=p.get(j+i-1);
            for(int j = 0; j < p.size()-1; j++)
                next[p.get(j)]=p.get(j+1);
            if(p.size()>=i)
            {
                inc(p.get(i-1)+1,1);
                if(p.size()>i)
                    inc(p.get(i)+1,-1);
            }
        }
        //querys
        Q[] q = new Q[m];
        for(int i = 0; i < m; i++)
        {
            q[i] = new Q(nextInt()-1,nextInt()-1,i);
        }
        Arrays.sort(q);
        int current = 0;
        
        while(current < m && q[current].l==0)
        {
            q[current].answer = sum(1,q[current].r+1);
            current++;
        }
        for(int i = 1; i < n; i++)
        {
            //update
            if(nextx[i-1]!= -1)
            {
                inc(nextx[i-1]+1,-1);
                if(next[nextx[i-1]]!=-1)
                {
                    inc(next[nextx[i-1]]+1,2);
                    if(next[next[nextx[i-1]]]!=-1)
                        inc(next[next[nextx[i-1]]]+1,-1);
                }
            }
            //compute answers
            while(current < m && q[current].l==i)
            {
                q[current].answer = sum(i+1,q[current].r+1);
                current++;
            }
        }
        int[] sol = new int[m];
        for(int i = 0; i < m; i++)
            sol[q[i].pos] = q[i].answer;
        for(int i = 0; i < m; i++)
            out.println(sol[i]);
    }
    public static void main(String[] args) throws NumberFormatException, IOException 
    {
        new D();
    }
    String nextToken() throws IOException
    {
        if(tok ==null || !tok.hasMoreTokens()) tok = new StringTokenizer(in.readLine());
        return tok.nextToken();
    }
    int nextInt() throws NumberFormatException, IOException
    {
        return Integer.parseInt(nextToken());
    }
    long nextLong() throws NumberFormatException, IOException
    {
        return Long.parseLong(nextToken());
    }
    double nextDouble() throws NumberFormatException, IOException
    {
        return Double.parseDouble(nextToken());
    }
}
