求Hack

#include<bits/stdc++.h>
#define int long long
#define ls (p<<1)
#define rs (p<<1|1) 
#define mid (l+r>>1)
#define PII pair<int,int>
#define ft first
#define sd second 
using namespace std;	
const int N=200005;
int n,m;
int a[N];
int t,block;	
int pos[N];
struct node{
	int i,l,r;
} q[N];
bool cmp(node a,node b){
	if(pos[a.l]!=pos[b.l]) return a.l<b.l;
	return a.r<b.r;
}
int sum[N];
int ANS=0,last=0;
int ans[N];
void add(int x){
	sum[a[x]]++;
	if(a[x]>=ANS) last++;
	while(last-sum[ANS]>=ANS+1){
		last-=sum[ANS];
		ANS++;
	}
//	cout<<ANS<<'\n';
}
void erase(int x){
	sum[a[x]]--;
	if(a[x]>=ANS) last--;
	while(last<ANS){
		ANS--;
		last+=sum[ANS];
	}
}
signed main(){
	cin>>n>>m;
	block=sqrt(n);
	t=n/block;
	if(n%block) t++;
	for(int i=1;i<=n;i++){
		cin>>a[i]; 
		pos[i]=(i-1)/block+1;
	}
	for(int i=1;i<=m;i++){
		cin>>q[i].l>>q[i].r;
		q[i].i=i;
	}
//	cout<<'\n';
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
//		cout<<q[i].l<<' '<<q[i].r<<'\n';
		while(l<q[i].l) erase(l++);
		while(r>q[i].r) erase(r--);
		while(l>q[i].l) add(--l);
		while(r<q[i].r) add(++r);
		ans[q[i].i]=ANS;
	} 
	for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
    return 0;
}