#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int K=500;
int n,m,belong[N],a[N],cnt[N],block_num[N],ans[N];
struct query
{
	int l,r,id;
}ask[N];
bool cmp(query a,query b)
{
	if(belong[a.l]==belong[b.l]) return a.r<b.r;
	return belong[a.l]<belong[b.l];
}
void add(int x)
{
	if(!cnt[x]) block_num[x/K]++;
	cnt[x]++;
}
void del(int x)
{
	if(cnt[x]==1) block_num[x/K]--;
	cnt[x]--;
}
void calc(int x)
{
	for(int i=1;i<=K;i++)
	{
		if(block_num[i-1]!=K)
		{
			for(int j=(i-1)*K;j<=i*K-1;j++)
			{
				if(!cnt[j])
				{
					ans[ask[x].id]=j;
					return;
				}
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	int block_size=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		a[i]=min(a[i],n+1);
		belong[i]=(i-1)/block_size+1;
	}
	for(int i=1;i<=m;i++)
	{
		cin>>ask[i].l>>ask[i].r;
		ask[i].id=i;
	}
	sort(ask+1,ask+1+m,cmp);
	int curL=ask[1].l,curR=ask[1].r;
	for(int i=curL;i<=curR;i++) add(a[i]);
	for(int i=2;i<=m;i++)
	{
		while(curL<ask[i].l) del(a[curL++]);
		while(curL>ask[i].l) add(a[--curL]);
		while(curR<ask[i].r) add(a[++curR]);
		while(curR>ask[i].r) del(a[curR--]);
		calc(i);
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}