思路是先用一个 umap维护后缀 mex ，然后在处理每一个块内的询问时，用第二个 umap 来维护左端点为 blockl 的 mex ，随着询问左移右端点，用第三个 umap 右移左端点，询问完成后，回滚到第二个 umap。

#include<bits/stdc++.h>

using namespace std;

int n,m,tmp;
vector<int> arr;

int block(int x){
	return (x-1)/tmp+1;
}

int blockl(int x){
	return (x-1)*tmp+1;
}

int blockmax;

void inputa(){
	cin>>n>>m;
	tmp=sqrt(n);
	arr.resize(n+1);
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	blockmax=block(n);
}

unordered_map<int,int> base;
int baseanswer=0;
int l=1;

void add(int x){
	base[x]++;
	while(base[baseanswer]!=0){
		baseanswer++;
	}
}

void erase(int x){
	base[x]--;
	if(base[x]==0){
		baseanswer=min(baseanswer,x);
	}
}

void init(){
	for(int i=1;i<=n;i++){
		add(arr[i]);
	}
}

struct ask{
	int now;
	int l,r;
};

int cmp(ask a,ask b){
	return a.r>b.r;
}

vector<int> answers;
vector<vector<ask>> groups;

void inputask(){
	groups.resize(blockmax+1);
	answers.resize(m+1);
	for(int i=1;i<=m;i++){
		ask a;
		cin>>a.l>>a.r;
		a.now=i;
		groups[block(a.l)].push_back(a);
	}
	for(int i=1;i<=blockmax;i++){
		sort(groups[i].begin(),groups[i].end(),cmp);
	}
}

void solveatask(int x){
	while(l<blockl(x)){
		erase(arr[l]);
		l++;
	}
	unordered_map<int,int > taskbase=base;
	int taskanswer=baseanswer;
	int r=n;
	for(auto i:groups[x]){
		while(r>i.r){
			taskbase[arr[r]]--;
			if(taskbase[arr[r]]==0){
				taskanswer=min(taskanswer,arr[r]);
			}
			r--;
		}
		unordered_map<int,int> tmpbase=taskbase;
		int tmpanswer=taskanswer;
		int nowl=blockl(x);
		while(nowl<i.l){
			tmpbase[arr[nowl]]--;
			if(tmpbase[arr[nowl]]==0){
				tmpanswer=min(tmpanswer,arr[nowl]);
			}
			nowl++;
		}
		answers[i.now]=tmpanswer;
	}
}

int main(){
	inputa();
	init();
	inputask();
	for(int i=1;i<=blockmax;i++){
		solveatask(i);
	}
	for(int i=1;i<=m;i++){
		cout<<answers[i]<<"\n";
	}
} 

/*
7 7
0 0 0 1 2 3 4
0 5
2 4
3 7
1 3
4 6
5 5
2 7
*/