#include<bits/stdc++.h>
#define int long long
#define inf 1e12
const int sz=1e6+5;
const int mod=1e9+7;
using namespace std;
int read() {
	char c=getchar();
	int r=0,f=1;
	while((c<'0'||c>'9')&&c!='-')
		c=getchar();
	if(c=='-') {
		f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		r=r*10+c-'0';
		c=getchar();
	}
	return f*r;
}
int a[sz],len,n,m,num[sz],R[sz],L[sz],cnt[sz],b[sz],Ans[sz],tot,maxb,maxn=0;
struct node
{
	int l,r,pos,id;
}t[sz];
bool cmp(node x,node y)
{
	if(x.l==y.l) return x.r<y.r;
	else return x.l<y.l;
}
bool cmp1(int x,int y)
{
	return x<y;
}
void pre()
{
	sort(num+1,num+1+n,cmp1);sort(t+1,t+1+m,cmp);
    tot=unique(num+1,num+1+n)-num-1;
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(num+1,num+1+tot,a[i])-num;
	maxb=n/len;
	L[1]=1,R[1]=L[1]+len-1;
    for(int i=2;i<=maxb;i++)
    L[i]=R[i-1]+1,R[i]=L[i]+len-1;
    if(R[maxb]<n) R[++maxb]=n,L[maxb]=R[maxb-1]+1;
    for(int i=1;i<=maxb;i++)
    	for(int j=L[i];j<=R[i];j++)   	   b[j]=i;
}
void force(int l,int r,int id)
{
    memset(cnt,0,sizeof(cnt));
	for(int i=l;i<=r;i++)
			cnt[a[i]]++;
 	for(int i=1;i<=tot;i++)
	{
		if(!cnt[i]) {			
		Ans[id]=num[i];
		break;	
		}					
    }
	for(int i=l;i<=r;i++)
    	cnt[a[i]]--;
}
signed main() {
   n=read(),m=read();
   len=sqrt(n);
   for(int i=1;i<=n;i++) a[i]=read(),num[i]=a[i],maxn=max(maxn,num[i]);
   for(int i=1;i<=m;i++) t[i].l=read(),t[i].r=read(),t[i].pos=t[i].l/len+1,t[i].id=i;
   pre();
//   for(int i=1;i<=n;i++) cout<<a[i]<<" ";
//   cout<<endl;
   int now=1;
   for(int i=1;i<=maxb;i++)
   {
    memset(cnt,0,sizeof(cnt));
	int r=R[i],tmp,nowm=-1;
	while(b[t[now].l]==i)
	{   			
//	    if(i==2) cout<<t[now].id<<"giao"<<endl;
		if(b[t[now].l]==b[t[now].r]) 
		{
			force(t[now].l,t[now].r,t[now].id);
			now++;
		    continue;
		}
		else
		{
		    int l=R[i]+1;
			while(r<t[now].r) cnt[a[++r]]++;
			if(cnt[nowm]||nowm==-1) 
		    {
				nowm=-1;
				for(int j=1;j<=tot;j++)
		    	{
				   if(!cnt[j]){   
				 	  nowm=j;
			          break;
				 	}		
     			}	
		    }
			tmp=nowm;		
			while(l>t[now].l)  cnt[a[--l]]++;
			if(cnt[nowm]||nowm==-1)
			{   
		        nowm=-1;
				for(int j=1;j<=tot;j++)
                    if(!cnt[j]){
					nowm=j;
                      break;
					}		
            }
			if(nowm==-1) Ans[t[now].id]=maxn+1;		
		    else Ans[t[now].id]=num[nowm];
		    nowm=tmp;
		    while(l<=R[i]) --cnt[a[l++]];
// 		    cout<<nowm<<endl;
			now++;
		 }   		
    }   
   }
  for(int i=1;i<=m;i++) cout<<Ans[i]<<endl;
//  cout<<tot<<"giao"<<endl;
}
/*
5 1
2 1 0 2 1
3 5
*/