#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=2e5+2;
int n,m,a[maxn];
struct node{
	int l,r,id;
}q[maxn];
int ans[maxn],b[maxn];
bool cmp(node a,node c){
	if(b[a.l]==b[c.l]){
		return a.r<c.r;
	}else{
		return a.l<c.l;
	}
}
int tree[maxn*8],num[maxn*8];
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
void pushup(int rt,int l,int r){
	tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
void update(int rt,int l,int r,int p,int val){
	if(l==r){
		num[rt]+=val;
		if(num[rt]==0)tree[rt]=0;
		else tree[rt]=1;
		return ;
	}
	if(p<=mid){
		update(lson,p,val);
	}else{
		update(rson,p,val);
	}
	pushup(rt,l,r);
//	cout<<l<<" "<<r<<" "<<tree[rt]<<"\n";
	return ;
}
int query(int rt,int l,int r){
//	cout<<l<<" "<<r<<" "<<tree[rt]<<"\n";
	if(l==r){
//		cout<<tree[rt]<<'\n';
		return l;
	}
	if(tree[rt<<1]<(mid-l+1)){
		query(lson);
	}else{
		query(rson);
	}
}
int main(){
	cin>>n>>m;
	int block=sqrt(n);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=(i-1)/block+1;
	}
	for(int i=1;i<=m;i++){
		cin>>q[i].l>>q[i].r;
		q[i].id=i;
	}
	sort(q+1,q+1+n,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		while(l<q[i].l)update(1,0,maxn-1,a[l++],-1);
		while(l>q[i].l)update(1,0,maxn-1,a[--l],1);
		while(r>q[i].r)update(1,0,maxn-1,a[r--],-1);
		while(r<q[i].r)update(1,0,maxn-1,a[++r],1);
		ans[q[i].id]=query(1,0,maxn-1);
//		cout<<l<<"  "<<r<<"\n";
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}