#include<cstdio>
#include<algorithm>
#define lc lson[p]
#define rc rson[p]
#define N 2019810
using namespace std;
int n,m,a[N];
struct Chairman_tree{
	int tot,rt[N],lson[N],rson[N],sum[N];
	void build(int &p,int l,int r){
		if(!p)p=++tot;
		if(l==r)return;
		int mid=(l+r)/2;
		build(lc,l,mid);
		build(rc,mid+1,r);
	}
	void insert(int &p,int pre,int l,int r,int x){
		if(!p)p=++tot;
		sum[p]=sum[pre]+1;
		if(l==r)return;
		int mid=(l+r)/2;
		if(x<=mid)insert(lc,lson[pre],l,mid,x);
		else insert(rc,rson[pre],mid+1,r,x);
	}
	int query(int p,int b,int l,int r,int k){
		if(l==r)return l;
		int mid=(l+r)/2,res=0;
		int sl=sum[lc]-sum[lson[b]],sr=sum[rc]-sum[rson[b]];
		if(sl>=k)res=query(lc,lson[b],l,mid,k);
		else if(sr>=k)res=query(rc,rson[b],mid+1,r,k);
		return res;
	}
}st;
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
//	st.build(st.rt[0],1,n);
	for(int i=1;i<=n;i++)st.insert(st.rt[i],st.rt[i-1],1,n,a[i]);
	while(m--){
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",st.query(st.rt[r],st.rt[l-1],1,n,(r-l+1)/2+1));
	}
	return 0;
}