#include<bits/stdc++.h> 
#define il inline 
#define debug() puts("-----")
using namespace std; 
il 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<<1)+(x<<3)+(ch^48),ch=getchar(); 
	return x*f; 
} 
const int N=5e5+10,V=720; 
int n,m; 
int len; 
int a[N]; 
int id[N]; 
int up,Len; 
int ans[N]; 
int L[N],R[N]; 
struct Que{ 
	int l,r,id; 
	il bool operator<(const Que& Liny)const{ 
		if(l/len!=Liny.l/len) return l<Liny.l; 
		return (l&len)?r<Liny.r:r>Liny.r; 
	} 
}q[N]; 
struct Node{ 
	int l,r; 
	int w,tag; 
}tr[V][V<<2]; int pid; 
int Tr[N]; 
#define low(x) x&-x 
il void Add(int x,int k){ 
	for(int i=x;i<=id[up];i+=low(i)) Tr[i]+=k; 
} 
il int qry(int x){ 
	int res=0; 
	for(int i=x;i;i-=low(i)) res+=Tr[i]; 
	return res; 
} 
il void pushdown(int u){ 
	if(!tr[pid][u].tag) return ; 
	tr[pid][u<<1].w+=tr[pid][u].tag,tr[pid][u<<1|1].w+=tr[pid][u].tag; 
	tr[pid][u<<1].tag+=tr[pid][u].tag,tr[pid][u<<1|1].tag+=tr[pid][u].tag; 
	tr[pid][u].tag=0; 
} 
il void build(int u,int l,int r){ 
	tr[pid][u]={l,r}; 
	if(l==r){ 
		tr[pid][u].w=L[pid]+l-2; 
		return ; 
	} int mid=l+r>>1; 
	build(u<<1,l,mid),build(u<<1|1,mid+1,r); 
	tr[pid][u].w=min(tr[pid][u<<1].w,tr[pid][u<<1|1].w); 
} 
il void modify(int u,int l,int r,int tag){ 
	if(l<=tr[pid][u].l&&tr[pid][u].r<=r){ 
		tr[pid][u].w+=tag; 
		tr[pid][u].tag+=tag; 
		return ; 
	} pushdown(u); 
	int mid=tr[pid][u].l+tr[pid][u].r>>1; 
	if(l<=mid) modify(u<<1,l,r,tag); 
	if(r>mid) modify(u<<1|1,l,r,tag); 
	tr[pid][u].w=min(tr[pid][u<<1].w,tr[pid][u<<1|1].w); 
} 
il int query(int u,int l,int r){ 
	if(l<=tr[pid][u].l&&tr[pid][u].r<=r) return tr[pid][u].w; 
	pushdown(u); 
	int w=1e9,mid=tr[pid][u].l+tr[pid][u].r>>1; 
	if(l<=mid) w=query(u<<1,l,r); 
	if(r>mid) w=min(w,query(u<<1|1,l,r)); 
	return w; 
} 
il void add(int x,int k){ 
//	cout<<x<<" ded "<<-k<<endl; 
	if(x!=R[id[x]]) pid=id[x],modify(1,x-L[id[x]]+2,R[id[x]]-L[id[x]]+1,-k); 
	Add(id[x]+1,-k); 
} 
il int calc(){ 
	for(int i=id[up];i>=1;i--){ 
		pid=i; 
		int w=query(1,1,R[i]-L[i]+1),tag=qry(i)-qry(i-1); 
//		cout<<i<<" "<<w<<" "<<tag<<endl; 
		if(w+tag<=0){ 
			for(int j=R[i];j>=L[i];j--){ 
//				cout<<j<<" "<<query(1,j-L[i]+1,j-L[i]+1)<<endl; 
				if(query(1,j-L[i]+1,j-L[i]+1)+tag<=0) return j; 	
			} break; 
		} 
	} return 0; 
} 
signed main(){ 
	n=read(),m=read(); len=sqrt(n); 
	for(int i=1;i<=n;i++) a[i]=read()+1,up=max(up,a[i]); 
	up=max(up,n),up++; Len=sqrt(up); 
	for(int i=1;i<=up;i++) id[i]=(i-1)/Len+1; 
	for(int i=1;i<=id[up];i++){ 
		L[i]=(i-1)*Len+1,R[i]=i*Len; 
		pid=i,build(1,1,R[i]-L[i]+1); 
	} for(int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].id=i; 
	sort(q+1,q+m+1); int l=1,r=0; 
	for(int i=1;i<=m;i++){ 
		while(l>q[i].l) add(a[--l],1); 
		while(r<q[i].r) add(a[++r],1); 
		while(l<q[i].l) add(a[l++],-1); 
		while(r>q[i].r) add(a[r--],-1); 
		ans[q[i].id]=calc(); 
	} for(int i=1;i<=m;i++) printf("%d\n",ans[i]-1); 
	return 0; 
} /*
3 3
0 0 2
1 3
2 3
3 3

3 1
0 0 2 
2 3
*/