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.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class MoAlgorithm {

    // Queries: Given L and R, find the number of distinct values in [L, R]
    static int ans;				// answer of the current range
    static int[] count;			// count[i] = frequency of value i in the current range

    static void add(int val,int inc)
    {
        if (val>100000)return;

       if (count[val]==val)--ans;
       count[val]+=inc;
        if (count[val]==val)++ans;


    }



    static int[] mo(int[] a, Query[] queries)
    {
        Query.s = (int) Math.ceil(Math.sqrt(a.length));
        Arrays.sort(queries);

        int L = 0, R = -1, res[] = new int[queries.length];
        for(Query q: queries)
        {

            while(L < q.left)  add(a[L++],-1);
            while(R > q.right) add(a[R--],-1);
            while(R < q.right) add(a[++R],1);
            while(L > q.left)  add(a[--L],1);
            res[q.idx] = ans;
        }
        return res;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        try(PrintWriter or= new PrintWriter(System.out)){
            StringTokenizer stringTokenizer= new StringTokenizer(br.readLine());
            int n=Integer.parseInt(stringTokenizer.nextToken()),m=Integer.parseInt(stringTokenizer.nextToken());

            count= new int[100009];
            int[] a= new int[n];
            stringTokenizer= new StringTokenizer(br.readLine());
            int p=0;
            while (stringTokenizer.hasMoreTokens()){
                a[p++]=Integer.parseInt(stringTokenizer.nextToken());
            }
            Query[] queries= new Query[m];
            for (int i = 0; i < m; i++) {
                stringTokenizer= new StringTokenizer(br.readLine());
                queries[i]=new Query(Integer.parseInt(stringTokenizer.nextToken())-1,
                        Integer.parseInt(stringTokenizer.nextToken())-1 ,i);
            }
            int [] ans= mo(a,queries);

            for (int i :ans) {
                or.println(i);
            }

        }
    }

    static class Query implements Comparable<Query>
    {
        static int s;				// length of a block , s = sqrt(n)
        int left, right, idx;

        Query(int a, int b, int c)
        {
            left = a; right = b; idx = c;
        }

        public int compareTo(Query q)
        {
            if(left / s != q.left / s)
                return left / s - q.left / s;
            return right - q.right;
        }
    }
}