Code:

#include <algorithm>
#include <cstdio>
#include <cmath>
#define fo(i_,j_,k_) for(int i_=j_;i_<=k_;++i_)
#define fr(i_,j_,k_) for(int i_=j_;i_>=k_;--i_)
#define It(type_) type_::iterator
#define rg register
#define rtn return
#define il inline
//#-st
typedef long long ll;
const int kMaxn=1000001;
//Constant
struct Query
{
	int l,r,id;
}q[kMaxn];
int cnt[kMaxn],bel[kMaxn],a[kMaxn],ans[kMaxn],Ans,l(1),r,n,m;
//Var
bool cmp(Query a,Query b)
{
	return bel[a.l]^bel[b.l]?a.l<b.l:(bel[a.l]&1?a.r<b.r:a.r>b.r);
}
il void add(int x)
{
	if(a[x]>n)rtn;
	if(cnt[a[x]]==a[x])--Ans;
	++cnt[a[x]];
	if(cnt[a[x]]==a[x])++Ans;
	rtn;
}
il void del(int x)
{
	if(a[x]>n)rtn;
	if(cnt[a[x]]==a[x])--Ans;
	--cnt[a[x]];
	if(cnt[a[x]]==a[x])++Ans;
	rtn;
}
il int Qread(void)
{
	int x=0;
	char c(getchar());
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	rtn x;
}
void Qwrite(int x)
{
	if(x>9)Qwrite(x/10); 
	putchar(x%10+'0');
	rtn;
}
//Functions
int main()
{
	n=Qread(),m=Qread();
	int block_size=sqrt(n); 
	fo(i,1,n)a[i]=Qread(),bel[i]=(i-1)/block_size+1;
	fo(i,1,m)q[i].l=Qread(),q[i].r=Qread(),q[i].id=i;
	std::sort(q+1,q+1+m,cmp);
	fo(i,1,m)
	{
		while(l<q[i].l)del(l++);
		while(l>q[i].l)add(++l);
		while(r<q[i].r)add(++r);
		while(r>q[i].r)del(r--);
		ans[q[i].id]=Ans;
	}
	fo(i,1,m)
		Qwrite(ans[i]),putchar('\n');
	rtn 0;
}
//MainFunction

RE #2