妹子回滚莫队0pts 悬我QQ

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int n,m,len,a[maxn],ans[maxn],tong[maxn],f[maxn];
struct p{
	int l,r,id;
}t[maxn];
int cmp(p u,p v){
	if(u.l/len==v.l/len)return u.r>v.r;
	return u.l<v.l;
}
int wok(int x){
	return (x-1)/len;
}
int main(){
	std::ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m; len=sqrt(n);
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++){
		cin>>t[i].l>>t[i].r; t[i].id=i;
	}
	sort(t+1,t+1+m,cmp);
	int l=1,r=1,mex=0; tong[a[1]]++;
	if(a[1]==0)mex=1; 
	for(int i=1;i<=n;i++)tong[a[i]]++;
	for(int i=0;i<2e5;i++){
		if(tong[i]==0){
			f[1]=i; break;
		}
	}
	for(int i=1;i<=n;i++){
		tong[a[i]]--;
		if(tong[a[i]]==0&&a[i]<f[i]){
			f[i+1]=a[i];
		}
		else f[i+1]=f[i];
	}
	for(int i=1;i<=m;i++){
		if(wok(t[i].l)!=wok(t[i-1].l)){
			while(l<wok(t[i].l)*len+1){
				tong[a[l]]--; l++;
			}
			while(r<n){
				r++;
				tong[a[r]]++;
			}
			mex=f[wok(t[i].l)*len+1];
		}
		int mnow=mex;
		while(l>wok(t[i].l)*len+1){
			l--; tong[a[l]]++;
		}
		while(l<t[i].l){
			tong[a[l]]--;
			if(a[l]<mnow&&tong[a[l]]==0){
				mnow=a[l];
			}
			l++;
		}
		while(r>t[i].r){
			tong[a[r]]--;
			if(a[r]<mnow&&tong[a[r]]==0){
				mnow=a[r]; 
			}
			if(a[r]<mex&&tong[a[r]]==0)mex=a[r];
			r--;
		}
		ans[t[i].id]=mnow;
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
	return 0;
}