Little Elephant and Array CodeForces – 220B （莫队）

The Little Elephant loves playing with arrays. He has array a, consisting of npositive integers, indexed from 1 to n. Let’s denote the number with index i as a_i.

Additionally the Little Elephant has m queries to the array, each query is characterised by a pair of integers l_j and r_j (1 ≤ l_j ≤ r_j ≤ n). For each query l_j, r_jthe Little Elephant has to count, how many numbers x exist, such that number xoccurs exactly x times among numbers a_lj, a_lj + 1, …, a_rj.

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 ≤ 10⁵) — the size of array a and the number of queries to it. The next line contains n space-separated positive integers a₁, a₂, …, a_n (1 ≤ a_i ≤ 10⁹). 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 l_j and r_j (1 ≤ l_j ≤ r_j ≤ 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题意:
问区间内含有出现次数等于其值的数字个数
思路：
莫队。
没有什么值得解释的，只不过预处理离散化将时间由3790 ms优化到186 ms，必须写一个博客纪念一下。

 #include<iostream>
 #include<algorithm>
 #include<vector>
 #include<stack>
 #include<queue>
 #include<map>
 #include<set>
 #include<cstdio>
 #include<cstring>
 #include<cmath>
 #include<ctime>
 #define fuck(x) cout<<#x<<" = "<<x<<endl;
 #define debug(a,i) cout<<#a<<"["<<i<<"] = "<<a[i]<<endl;
 #define ls (t<<1)
 #define rs ((t<<1)+1)
 using namespace std;
 typedef long long ll;
 typedef unsigned long long ull;
 const int maxn = ;
 const int maxm = ;
 const int inf = 2.1e9;
 const ll Inf = ;
 const int mod = ;
 const double eps = 1e-;
 const double pi = acos(-);
 int num[maxn];
 struct node{
     int l,r;
     int id;
 }a[maxm];
 int anss[maxm];
 int block; bool cmp(node a,node b){
     return (a.l/block!=b.l/block)?a.l<b.l:a.r<b.r;
 }
 int vis[];
 int rem[maxn],cnt;
 int pos[maxn];
 int get_id(int x){
     return lower_bound(rem+,rem++cnt,x)-rem;
 } int main()
 {
     int n;
     scanf("%d",&n);
     int m;
     scanf("%d",&m);
     for(int i=;i<=n;i++){
         scanf("%d",&num[i]);
         rem[i]=num[i];
     }
     block=sqrt(n);
     for(int i=;i<=m;i++){
         scanf("%d%d",&a[i].l,&a[i].r);
         a[i].id=i;
     }     sort(a+,a++m,cmp);
     sort(rem+,rem++n);     cnt=unique(rem+,rem++n)-rem-;
     for(int i=;i<=n;i++){
         pos[i]=get_id(num[i]);
     }
     int L=,R=;
     int ans=;
     num[]=-;
     for(int i=;i<=m;i++){
         while(R<a[i].r){
             R++;
             if(vis[pos[R]]==num[R]){ans--;}
             vis[pos[R]]++;
             if(vis[pos[R]]==num[R]){ans++;}
         }
         while(L<a[i].l){
             if(vis[pos[L]]==num[L]){ans--;}
             vis[pos[L]]--;
             if(vis[pos[L]]==num[L]){ans++;}
             L++;         }
         while(R>a[i].r){
             if(vis[pos[R]]==num[R]){ans--;}
             vis[pos[R]]--;
             if(vis[pos[R]]==num[R]){ans++;}
             R--;
         }
         while(L>a[i].l){
             L--;
             if(vis[pos[L]]==num[L]){ans--;}
             vis[pos[L]]++;
             if(vis[pos[L]]==num[L]){ans++;}
         }
         anss[a[i].id]=ans;
     }
     for(int i=;i<=m;i++){
         printf("%d\n",anss[i]);
     }
     return ;
 }