#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<set> 
using namespace std;
const int N=200000;
int n,a[N+5],t,bl,f[N+5],nowa;
set<int> st;
struct node{
	int l,r,id,ans;
}q[N+5]; 
bool cmp1(node u,node v){
	if (u.l/bl==v.l/bl) return u.r<v.r;
	return u.l/bl<v.l/bl;
}
bool cmp2(node u,node v){
	return u.id<v.id;
}
void add(int x){
	f[a[x]]++;
	if (f[a[x]]==1) st.erase(a[x]),nowa=*st.begin(); 
}
void del(int x){
	f[a[x]]--;
	if (f[a[x]]==0) st.insert(a[x]),nowa=*st.begin();
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	for (int i=0;i<=N+1;i++) st.insert(i);
	cin>>n>>t; bl=sqrt(n); 
	for (int i=1;i<=n;i++) cin>>a[i];
	for (int i=1;i<=t;i++){//t
		cin>>q[i].l>>q[i].r;
		q[i].id=i;
	}
	sort(q+1,q+t+1,cmp1);//t
	int L=1,R=0,nowb=0;
	for (int i=1;i<=t;i++){//t
		int l=q[i].l,r=q[i].r;
		if (l/bl>nowb) {nowb=l/bl; while (R>r) del(--R);}//nowb
		while (L>l) add(--L);//
		while (R<r) add(++R);//++first
		while (L<l) del(L++);
		q[i].ans=nowa;
	}
	sort(q+1,q+t+1,cmp2);//t
	for (int i=1;i<=t;i++) cout<<q[i].ans<<'\n';
}