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 static java.lang.Integer.compare;
import static java.util.Arrays.deepToString;

/*
 *
 *18/5/18
 *6:27 PM
 *remedy441
 *
 */

/*
* Reference: https://blog.anudeep2011.com/mos-algorithm/
* http://www.spoj.com/problems/DQUERY/ --
* http://codeforces.com/contest/86/problem/D --
* https://www.codechef.com/problems/IITI15 -
* http://codeforces.com/contest/220/problem/B --
* http://codeforces.com/contest/446/problem/C -
* http://codeforces.com/problemset/problem/375/D
* http://codeforces.com/problemset/problem/351/D -
* https://www.codechef.com/MARCH14/problems/GERALD07
* https://www.codechef.com/problems/GERALD3
*
* */
public class MosAlgo {


    static int cnt [];
    static long ans;
    static HashMap<Integer,Integer>hmp;
    static void add(int po){
        int pos = hmp.get(po);
        cnt[pos]++;
        if(cnt[pos]==po)
            ans++;
        if(cnt[pos]==po+1)
            ans--;

    }
    static void remove(int po){
        int pos = hmp.get(po);
        cnt[pos]--;
        if(cnt[pos]==po)
            ans++;
        if(cnt[pos]==po-1)
            ans--;
    }

    public static void main(String args[]){

        InputReader in = new InputReader(System.in);
        FastReader fs = new FastReader();
        PrintWriter out = new PrintWriter(System.out);
        //int n = fs.nextInt();
        int n = in.ni();
        int q = in.ni();
        int ar[] = new int[n];
        hmp = new HashMap<>();
        int cnts =0;
        for(int i=0;i<n;i++){
            ar[i] = in.ni();
            if(!hmp.containsKey(ar[i]))
                hmp.put(ar[i],cnts++);
        }
        cnt =new int[1000001];
        int x = (int)Math.sqrt(n);
        int BLOCK_SIZE = x;
        if(x*x!=n)
            BLOCK_SIZE++;
        BLOCK_SIZE = 555;
        //int q = in.ni();
        long anss[] = new long[q];
        ArrayList<Pair>pairs = new ArrayList<>();
        for(int i=0;i<q;i++){
            int a = in.ni()-1;
            int b = in.ni()-1;
            Pair p = new Pair(a,b,a/BLOCK_SIZE,i);
            pairs.add(p);
        }
        //debug(pairs);
        Collections.sort(pairs);
        //debug(pairs);
        int cl=0;
        int cr=0;
        ans = 0;
        for(Pair p : pairs){

            int l = p.L;
            int r = p.R;
            while(cl < l) {
                remove(ar[cl]);
                cl++;
            }
            while(cl > l) {
                add(ar[cl-1]);
                cl--;
            }
            while(cr <= r) {
                add(ar[cr]);
                cr++;
            }
            while(cr > r+1) {
                remove(ar[cr-1]);
                cr--;
            }
            //debug(ans,cnt);
            anss[p.I]=ans;
        }
        for(int i=0;i<q;i++)
            out.println(anss[i]);

        out.close();

    }

    public static void debug(Object... o) {
        System.out.println(deepToString(o));
    }

    static class Pair implements Comparable<Pair>{

        int L,R,B,I;

        public Pair(int l, int r, int b,int inx) {
            L = l;
            R = r;
            B = b;
            I=inx;
        }

        @Override
        public int compareTo(Pair o) {
            if(this.B!=o.B)
                return compare(this.B,o.B);
            else
                return compare(this.R,o.R);
        }

        @Override
        public String toString() {
            return L+" "+R;
        }
    }

    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
    static class InputReader {
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int snext() {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) {
                curChar = 0;
                try {
                    snumChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int ni() {
            int c = snext();
            while (isSpaceChar(c)) {
                c = snext();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nl() {
            int c = snext();
            while (isSpaceChar(c)) {
                c = snext();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int[] nIArr(int n) {
            int a[] = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }

        public long[] nLArr(int n) {
            long a[] = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }

        public String readString() {
            int c = snext();
            while (isSpaceChar(c)) {
                c = snext();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = snext();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public String nextLine() {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = snext();
            } while (!isEndOfLine(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }

    }
}
