#include<bits/stdc++.h>
//#define int long long
using namespace std;
inline int read()
{
   int x=0,f=1;char ch=getchar();
   while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
   while (ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
   return x*f;
}
void write(int x)
{
   if(x<0)putchar('-'),x=-x;
   if(x<10)putchar(x+'0');
   else write(x/10),putchar(x%10+'0');
}
const int N=2e5+5;
//const int mod=1e9+7;
int n,m,a[N],pos[N],t[N],len,cnt,id[N],ans[N];
bool v[N];
struct que
{
	int l,r,id,opk;
}q[N];
struct kuai
{
	int l,r;
}k[N];
bool cmp(que x,que y)
{
	if(id[x.l]==id[y.l])return x.r<y.r;
	return id[x.l]<id[y.l];
}
void  add(int x)
{
	t[a[x]]++;
	if(t[a[x]]==1)pos[id[a[x]]]++;
}
void del(int x)
{
	t[a[x]]--;
	if(t[a[x]]==0)pos[id[a[x]]]--;
}
int query()
{
	int op=1;
	for(int i=1;i<=cnt;i++)if(pos[i]!=k[i].r-k[i].l+1){op=i;break;}
	for(int i=k[op].l;i<=k[op].r;i++)if(!t[i])return i;
}
signed main()
{
	n=read();
	m=read();
	len=sqrt(n);
	id[0]=1;
	for(int i=1;i<=n;i++)
	{
		a[i]=min(read(),n+1);
		id[i]=(i-1)/len+1;
		if(id[i]!=id[i-1])
		{
			k[cnt].r=i-1;
			cnt++;
			k[cnt].l=i;
		}
	}
	k[1].l=0;
	id[n+1]=cnt;
	k[cnt].r=n+1;
	for(int i=1;i<=m;i++)
	{
		q[i].l=read();q[i].r=read();
		q[i].id=i;
		q[i].opk=id[i];
	}
	sort(q+1,q+m+1,cmp);
	int l=q[1].l,r=q[1].l-1;
//	for(int i=1;i<=m;i++)cout<<q[i].l<<" "<<q[i].r<<" "<<q[i].opk<<'\n';
	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--);
//		for(int i=0;i<=3;i++)cout<<pos[i]<<' ';
//		cout<<'\n';
		ans[q[i].id]=query();
	}
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}