#include<bits/stdc++.h>
using namespace std;
int read(){int x;scanf("%d",&x);return x;}
const int N = 5e5+100,inf = 3e5+10;
int ans = 0,c[N],val[N],pos[N],n,m;
struct Q{int l,r,id,Ans;}q[N];
void add(int x){
	if(val[x]>inf) return;
	c[val[x]]++;
//	int tt=0;
	 while(c[ans])
	 {
//	 	tt++;
//	 	cout<<ans<<" "<<val[x]<<endl;
//	 	if(tt==1) assert(ans==val[x]);
	 	ans++;
	 } 
}
void del(int x){
	if(val[x]>inf) return;
	c[val[x]]--;
	if(!c[val[x]] && ans>val[x]) ans=val[x]; 
}
bool cmp_work(Q a,Q b){
	if(pos[a.l] == pos[b.l]) {
		if(pos[a.l]&1) return a.r < b.r;
		else return a.r > b.r;
	}
	return a.l < b.l;
}
bool cmp_id(Q a,Q b){
	return a.id < b.id;
}
int main(){
	freopen("P4137_4.in","r",stdin);
	freopen("check.out","w",stdout);
	n = read();m = read();
	for(int i = 1;i <= n;i++) val[i] = read();
	int block = sqrt(n);
	for(int i = 1;i <= n;i++) {
		pos[i] = i/block + 1;
	}
	for(int i = 1;i <= m;i++){
		q[i].l = read();q[i].r = read();
		q[i].id = i;	
	}
	sort(q+1,q+1+m,cmp_work);
	for(int l = 1,r = 0,i = 1;i <= m;i++)
	{
		while(l > q[i].l) l--,add(l);
		while(l < q[i].l) del(l),l++;
		while(r > q[i].r) del(r),r--;
		while(r < q[i].r) r++,add(r);
		q[i].Ans = ans;
	}
	sort(q+1,q+1+m,cmp_id);
	for(int i = 1;i <= m;i++){
		printf("%d\n",q[i].Ans);
	}
	return 0;
}