#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,M=5e2+5;
int n,m,V=N,a[N],ans[N];
int block,tot,lt[M],rt[M],belong[N],sum[N],s[M];
struct QUE{
	int l,r,id;
}q[N];
bool cmp(QUE x,QUE y){
	if(belong[x.l]==belong[y.l]) return x.r<y.r;
	else return belong[x.l]<belong[y.l];
}
void build(){
	block=448;
	tot=n/block;
	if(n%block) tot++;
	for(int i=1;i<=tot;i++){
		lt[i]=(i-1)*block;
		rt[i]=i*block-1;
	}rt[tot]=n;
	for(int i=1;i<=n;i++) belong[i]=(i-1)/block+1;
}
void add(int x){
	s[a[x]]++;
	if(s[a[x]]==1) sum[belong[a[x]]]++;
}
void del(int x){
	if(s[a[x]]==1) sum[belong[a[x]]]--;
	s[a[x]]--;
}
int ask(){
	for(int i=0;i<block;i++){
        if(sum[i]!=block){
            for(int j=lt[i+1];j<=rt[i+1];j++){
                if(!s[j]){
                    return j;
                }
            }
        }
    }
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i],a[i]=min(a[i],n+1);
	build();
	for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r,q[i].id=i;
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		while(l>q[i].l) add(--l);
		while(r<q[i].r) add(++r);
		while(l<q[i].l) del(l++);
		while(r>q[i].r) del(r--);
		ans[q[i].id]=ask();
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
	return 0;
}