import math
from collections import defaultdict,deque
import heapq
import sys
import math
import bisect
def input():return sys.stdin.readline().strip()
def solve():
n,m=map(int,input().split())
arr=list(map(int,input().split()))
query=[[] for j in range(int(n**0.5)+1)]
q=[0]*m
for j in range(m):
x,y=map(int,input().split())
query[int(x/n**(0.5))].append((x-1,y-1,j))
q=deque()
for j in query:
j.sort(key=lambda x:(x[1]))
for p in j:
q.append(p)
d=defaultdict(lambda :0)
j=0
curl,curr,x=1,0,0
res=[0]*m
while j<len(q):
l,r=q[j][0],q[j][1]
while curl<l:
d[arr[curl]]-=1
if d[arr[curl]]==arr[curl]-1:
x-=1
if d[arr[curl]]==arr[curl]:
x+=1
curl+=1
while curl>l:
curl-=1
d[arr[curl]]+=1
if d[arr[curl]]==arr[curl]+1:
x-=1
if d[arr[curl]]==arr[curl]:
x+=1
while curr<r:
curr+=1
d[arr[curr]]+=1
if d[arr[curr]]==arr[curr]+1:
x-=1
if d[arr[curr]]==arr[curr]:
x+=1
while curr>r:
d[arr[curr]]-=1
if d[arr[curr]]==arr[curr]-1:
x-=1
if d[arr[curr]]==arr[curr]:
x+=1
curr-=1
res[q[j][2]]=x
j+=1
for j in res:
print(j)
if __name__ == '__main__':
solve()
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define vi vector<int>
#define pb push_back
struct miquery{
int ind;
int f;
int s;
};
int len = 0;
bool cmp(miquery &a, miquery &b){
if(a.f / len == b.f / len)
return a.s > b.s;
return a.f / len < b.f / len;
}
int main(){
int n, q;
cin>>n>>q;
vi a(n);
for(int i=0; i<n; i++){
cin>>a[i];
}
len = ceil(sqrt(n));
vector<miquery> que;
for(int i=0; i<q; i++){
int l, r;
cin>>l>>r;
l--; r--;
que.pb({i, l, r});
}
sort(que.begin(), que.end(), cmp);
int l = 0, r = -1;
unordered_map<int, int> mp;
int ans = 0;
vector<pair<int,int>> res;
for(int i=0; i<q; i++){
int indi = que[i].ind;
int st = que[i].f;
int en = que[i].s;
while(r < en){
r++;
mp[a[r]]++;
if(mp[a[r]] == a[r]) ans++;
if(mp[a[r]] == a[r] + 1) ans--;
}
while(r > en){
mp[a[r]]--;
if(mp[a[r]] == a[r]) ans++;
if(mp[a[r]] == a[r] - 1) ans--;
r--;
}
while(l > st){
l--;
mp[a[l]]++;
if(mp[a[l]] == a[l]) ans++;
if(mp[a[l]] == a[l] + 1) ans--;
}
while(l < st){
mp[a[l]]--;
if(mp[a[l]] == a[l]) ans++;
if(mp[a[l]] == a[l] - 1) ans--;
l++;
}
res.pb({indi, ans});
}
sort(res.begin(), res.end());
for(int i=0; i<q; i++){
cout<<res[i].second<<"\n";
}
}Health of a person | Divisibility |
A. Movement | Numbers in a matrix |
Sequences | Split houses |
Divisible | Three primes |
Coprimes | Cost of balloons |
One String No Trouble | Help Jarvis! |
Lift queries | Goki and his breakup |
Ali and Helping innocent people | Book of Potion making |
Duration | Birthday Party |
e-maze-in | Bricks Game |
Char Sum | Two Strings |
Anagrams | Prime Number |
Lexical Sorting Reloaded | 1514A - Perfectly Imperfect Array |
580A- Kefa and First Steps | 1472B- Fair Division |
996A - Hit the Lottery | MSNSADM1 Football |