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

public class TestClass {

    static class Parser
    {
        final private int BUFFER_SIZE = 1 << 16;

        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Parser(InputStream in)
        {
            din = new DataInputStream(in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public long nextLong() throws Exception
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = c == '-';
            if (neg) c = read();
            do
            {
                ret = ret * 10 + c - '0';
                c = read();
            } while (c > ' ');
            if (neg) return -ret;
            return ret;
        }

        //reads in the next string
        public String next() throws Exception
        {
            StringBuilder ret =  new StringBuilder();
            byte c = read();
            while (c <= ' ') c = read();
            do
            {
                ret = ret.append((char)c);
                c = read();
            } while (c > ' ');
            return ret.toString();
        }

        public int nextInt() throws Exception
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = c == '-';
            if (neg) c = read();
            do
            {
                ret = ret * 10 + c - '0';
                c = read();
            } while (c > ' ');
            if (neg) return -ret;
            return ret;
        }

        private void fillBuffer() throws Exception
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1) buffer[0] = -1;
        }

        private byte read() throws Exception
        {
            if (bufferPointer == bytesRead) fillBuffer();
            return buffer[bufferPointer++];
        }
    }
    static class OutputWriter
    {
        private PrintWriter writer;

        public OutputWriter(OutputStream stream)
        {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(
                    stream)));
        }

        public OutputWriter(Writer writer)
        {
            this.writer = new PrintWriter(writer);
        }

        public void println(int x)
        {
            writer.println(x);
        }

        public void print(int x)
        {
            writer.print(x);
        }

        public void println(char x)
        {
            writer.println(x);
        }

        public void print(char x)
        {
            writer.print(x);
        }

        public void println(int array[], int size)
        {
            for (int i = 0; i < size; i++)
                println(array[i]);
        }

        public void print(int array[], int size)
        {
            for (int i = 0; i < size; i++)
                print(array[i] + " ");
        }

        public void println(long x)
        {
            writer.println(x);
        }

        public void print(long x)
        {
            writer.print(x);
        }

        public void println(long array[], int size)
        {
            for (int i = 0; i < size; i++)
                println(array[i]);
        }

        public void print(long array[], int size)
        {
            for (int i = 0; i < size; i++)
                print(array[i]);
        }

        public void println(float num)
        {
            writer.println(num);
        }

        public void print(float num)
        {
            writer.print(num);
        }

        public void println(double num)
        {
            writer.println(num);
        }

        public void print(double num)
        {
            writer.print(num);
        }

        public void println(String s)
        {
            writer.println(s);
        }

        public void print(String s)
        {
            writer.print(s);
        }

        public void println()
        {
            writer.println();
        }

        public void printSpace()
        {
            writer.print(" ");
        }

        public void printf(String format, Object args)
        {
            writer.printf(format, args);
        }

        public void flush()
        {
            writer.flush();
        }

        public void close()
        {
            writer.close();
        }

    }
    static int ans[];
    static int block;
    static HashMap<Integer,Integer> map=new HashMap<>();
static class Query {
    int L;
    int R;
    int indx;
    Query(int L,int R,int indx){
        this.L=L;
        this.R=R;
        this.indx=indx;
    }
}
static void solve(int n,int arr[],Query Q[]){
    int block=(int)Math.sqrt(n);

    Arrays.sort(Q, new Comparator<Query>() {
        @Override
        public int compare(Query o1, Query o2) {
            if(o1.L/block==o2.L/block)
                return Integer.compare(o1.R,o2.R);
            else
                return Integer.compare(o1.L,o2.L);
        }
    });
    int s=0,t=-1;
    int ct[]=new int[100001];
    int cct=0;
    for (int i = 0; i <Q.length ; i++) {
        while (t<Q[i].R){
            t++;
            if(arr[t]<=100000){
                ct[arr[t]]++;
                if(ct[arr[t]]==arr[t]) cct++;
                if(ct[arr[t]]==arr[t]+1) cct--;
            }
        }
        while (s>Q[i].L){
            s--;
            if(arr[s]<=100000){
                ct[arr[s]]++;
                if(ct[arr[s]]==arr[s]) cct++;
                if(ct[arr[s]]==arr[s]+1) cct--;
            }
        }
        while (t>Q[i].R){
            if(arr[t]<=100000){
                ct[arr[t]]--;
                if(ct[arr[t]]==arr[t]) cct++;
                if(ct[arr[t]]==arr[t]-1) cct--;
            }
            t--;
        }
        while (s<Q[i].L){
            if(arr[s]<=100000){
                ct[arr[s]]--;
                if(ct[arr[s]]==arr[s]) cct++;
                if(ct[arr[s]]==arr[s]-1) cct--;
            }
            s++;
        }
            ans[Q[i].indx]=cct;

    }



}

    public static void main(String args[]) throws Exception {
        Parser s = new Parser(System.in);
        OutputWriter out = new OutputWriter(System.out);
        int N=s.nextInt();
        int Q=s.nextInt();
        ans=new int[Q];
        int arr[]=new int[N];
        for (int i = 0; i <N ; i++)
            arr[i]=s.nextInt();
        Query[] q=new Query[Q];
        for (int i = 0; i <Q ; i++) {
            int x=s.nextInt()-1;
            int y=s.nextInt()-1;
            q[i]=new Query(x,y,i);
        }
solve(N,arr,q);
        for (int i = 0; i <Q ; i++) {
           out.println(ans[i]);
        }out.close();


    }
}