RT

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<map>
#include<list>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;
#define mod 998244353
#define inf 0x3f3f3f3f
#define re register
#define maxn 200010
#define int long long
#define Orz cout<<"stO %王队% Orz"<<'\n';
int n,m,mx;
int a[maxn],ans[maxn];
struct node
{
	int l,r,k,be;
}q[maxn];
int cnt[maxn];
int tot,sum[maxn],L[maxn],R[maxn],be[maxn];
void init()
{
	int b=sqrt(mx)+1;
	tot=mx/b;
	if(mx%b)	tot++;
	for(re int i=1;i<=tot;++i)
		L[i]=(i-1)*b;
	for(re int i=1;i<=tot;++i)
		R[i]=i*b-1;
	for(re int i=0;i<=n;++i)	
		be[i]=i/b+1;
}
int query()
{
	for(re int i=1;i<=tot;++i)
		if(sum[i]!=(R[i]-L[i]+1))
			for(re int j=L[i];j<=R[i];++j)
				if(!cnt[j])	return j;
}
void add(int x)
{
	cnt[a[x]]++;
	if(cnt[a[x]]==1) sum[a[x]]++;
}
void sub(int x)
{
	cnt[a[x]]--;
	if(!cnt[a[x]])	sum[a[x]]--;
}
bool cmp(node x,node y)
{
	return (x.be^y.be)?x.be<y.be:(x.be&1)?x.r<y.r:x.r>y.r;
}
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-'0'; ch=getchar();}
    return x*f;
}
inline void wn(int x){if (x<0) {putchar('-');wn(-x);return;}if(x>=10)wn(x/10);putchar(x%10+'0');}
inline void wr(int x){wn(x);putchar('\n');}
inline void wi(int x){wn(x);putchar(' ');}
signed main()
{
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
//	printf("%dM\n",(sizeof(dp) >> 20));
	cin>>n>>m;
	int block=n/(sqrt(m*2/3)+1);
	for(re int i=1;i<=n;++i)	a[i]=read(),mx=max(mx,a[i]);
	for(re int i=1;i<=m;++i)	q[i].l=read(),q[i].r=read(),q[i].k=i,q[i].be=q[i].l/block;
	mx+=2;
	init();
	sort(q+1,q+m+1,cmp);
	re int l=1,r=0; 
	for(re int i=1;i<=m;++i)
	{
		while(q[i].l<l)	add(--l);
		while(q[i].l>l)	sub(l++);
		while(q[i].r<r)	sub(r--);
		while(q[i].r>r)	add(++r);
		ans[q[i].k]=query();
	}
	for(re int i=1;i<=m;++i)	wr(ans[i]);
	return 0;
}