#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<cctype>
#include<stack>
#include<set>
#include<map>
#include<climits>
#include<set>
using namespace std;
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
	return s*w;
}
inline void output(int x)
{
	if(x/10) output(x/10);
	putchar(x%10+'0');
	return;
}
const int INF=1e9;
typedef long long ll;
inline int Min(int x,int y){return x<y?x:y;}
inline int Max(int x,int y){return x>y?x:y;}
inline void Swap(int&x,int&y){x^=y;y^=x;x^=y;}
const int MAXN(2e5+10);
const int BLOCK(448);
int n,m,a[MAXN],cnt[MAXN];
int idx[MAXN];
struct Que{int l,r,pos;};
Que q[MAXN];
inline bool cmp(Que x,Que y){return (idx[x.l]^idx[y.l])?idx[x.l]<idx[y.l]:(idx[x.l]&1)?x.r<y.r:x.r>y.r;}
int num[MAXN];
inline void add(int x)
{
	if(++cnt[x]==1) --num[x/BLOCK];
	return;
}
inline void del(int x)
{
	if(--cnt[x]==0) ++num[x/BLOCK];
	return;
}
inline int getans()
{
	for(register int i=1;i<=BLOCK;i++)
		if(num[i-1]!=BLOCK)
		{
			int l=(i-1)*BLOCK,r=i*BLOCK;
			for(register int j=l;j<r;j++)
				if(!cnt[j]) return j;
		}
}
int ans[MAXN];
int main()
{
	srand(time(NULL));
	n=read(),m=read();
	const int B=sqrt(n);
	for(register int i=1;i<=n;i++) a[i]=read();
	for(register int i=1;i<=n;i++) idx[i]=i/B;
	for(register int i=1;i<=m;i++)
		q[i].l=read(),q[i].r=read(),q[i].pos=i;
	sort(q+1,q+1+m,cmp);
	int l(1),r(0);
	for(register int i=0;i<=2e5+1;i++) num[i/BLOCK]=1;
	for(register int i=1;i<=m;i++)
	{
		while(l>q[i].l) add(a[--l]);
		while(r<q[i].r) add(a[++r]);
		while(l<q[i].l) del(a[l++]);
		while(r>q[i].r) del(a[r--]);
		ans[q[i].pos]=getans();
	}
	for(register int i=1;i<=m;i++) output(ans[i]),putchar('\n');
	return 0;
}