#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int N=1e6+5;
struct node{
	ll l,r,id;
}e[N];
ll n,m,k,a[N],tr[N],ans[N],mp[N],mpl[N],B[N],maxx,cnt=1,qu,nxtl=1,nxtr;
bool cmp(node x,node y){
	if(x.l/qu==y.l/qu) return x.r<y.r;
	return x.l/qu<y.l/qu;
}
void add(ll x){
	mp[a[x]]++;
	if(mp[a[x]]==1) mpl[B[a[x]]]++;
}
void del(ll x){
	mp[a[x]]--;
	if(mp[a[x]]==0) mpl[B[a[x]]]--;	
}
void getans(ll id){
	for(int i=0;i<=B[maxx];i++) {
		if(mpl[i]<qu){
			for(int j=qu*i;j<=(i+1)*qu-1;j++){
				if(!mp[j]){
					ans[id]=j;
					return ;
				}
			}
		}		
	}
}
int main(){
//	freopen("P4137_2 (1).in","r",stdin);
//	freopen("mex","w",stdout);
	scanf("%lld%lld",&n,&m);
	qu=sqrt(n);
	for(int i=1;i<=n;i++) {
		scanf("%lld",&a[i]);
		maxx=max(maxx,a[i]);
	}
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",&e[i].l,&e[i].r);
		e[i].id=i;
	}
	sort(e+1,e+1+m,cmp);
	qu=sqrt(maxx);
	memset(ans,-1,sizeof(ans));
	for(int i=0;i<=n;i++) B[i]=i/qu;
	for(int i=1;i<=m;i++){
		while(nxtl>e[i].l) add(--nxtl);
		while(nxtr<e[i].r) add(++nxtr);
		while(nxtl<e[i].l) del(nxtl++);
		while(nxtr>e[i].r) del(nxtr--);
		getans(e[i].id);
		if(ans[e[i].id]==-1) ans[e[i].id]=maxx+1;
	}
	for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
	return 0;
}