D. Little Elephant and Array

time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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 numbersalj, 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 题意：询问区间[l,r]内出现次数等于它本身的数的个数 莫队算法

#include
        
         #include
         
          #include
          
           using namespace std;int n,m,siz,ans;int a[100001],hash[100001];int sum[100001];struct node{    int bl,id;    int l,r,k;}e[100001];bool cmp(node p,node q){    if(p.bl!=q.bl) return p.bl
           
            opl)  update(--l,1);        while(l
            
             opr)  update(r--,-1);         e[i].k=ans;    }        sort(e+1,e+m+1,cmp2);    for(int i=1;i<=m;i++) printf("%d\n",e[i].k);}