RT，我用的是set查询mex，T飞了

#include<bits/stdc++.h>

using namespace std;

namespace IO{
	char ibuf[(1<<20)+1],*iS,*iT;
	#if ONLINE_JUDGE
	#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
 	#else
	#define gh() getchar()
	#endif
	#define reg register
	inline long long read(){
		reg char ch=gh();
		reg long long x=0;
		reg char t=0;
		while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
		while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
		return t?-x:x;
	}
}
using IO::read;

set<int>s;

int n;
int a[1000010];
int m;
int B;
int sum;
int maxn;
int ans[1000010];
int vis[1000010];

struct node{
	int l,r,id;
}b[1000010];

inline bool cmp(node a,node b){
	return (a.l/B)^(b.l/B)?a.l<b.l:(((a.l/B)&1)?a.r<b.r:a.r>b.r);
}

inline void add(int x){
	if(!vis[a[x]]){
		s.erase(a[x]);
		sum=*s.begin();
	}
	vis[a[x]]++;
}

inline void del(int x){
	vis[a[x]]--;
	if(!vis[a[x]]){
		s.insert(a[x]);
		sum=*s.begin();
	}
}

int main(){
	n=read();
	m=read(); 
	for(register int i=1;i<=n;i++){
		a[i]=read();
		maxn=max(maxn,a[i]);
	}
	for(int i=1;i<=maxn+1;i++){
		s.insert(i);
	}
	B=n/sqrt(m*2/3)+1;
	for(register int i=1;i<=m;i++){
		b[i].l=read();
		b[i].r=read();
		b[i].id=i;
	}
	int l=1,r=0;
	sort(b+1,b+1+m,cmp);
	for(register int i=1;i<=m;i++){
		while(l>b[i].l) add(--l);
		while(r<b[i].r) add(++r);
		while(r>b[i].r) del(r--);
		while(l<b[i].l) del(l++);
		ans[b[i].id]=sum;
	}
	for(int i=1;i<=m;i++){
		printf("%d\n",ans[i]);
	}
	return 0;
}