#include<bits/stdc++.h>
#define mid ((r-l)>>1)+l
using namespace std;
const int N=5e5+5;
int n,m,x,y,node;
int a[N],b[N],root[N];
struct node{
	int l,r,val;
}tree[N<<5];
inline int build(int l,int r){
	node++;
	if(l==r)
		return node;
	tree[node].l=build(l,mid);
	tree[node].r=build(mid+1,r);
	return node;
}
inline int updata(int head,int l,int r,int x){
	node++;
	tree[node]=tree[head];
	tree[node].val++;
	if(l==r)
		return node;
	if(x<=mid)
		tree[node].l=updata(tree[head].l,l,mid,x);
	else
		tree[node].r=updata(tree[head].r,mid+1,r,x);
	return node;
}
inline int query(int head,int next,int l,int r,int rank){
	if(l==r)
		return b[l];
	if(rank<tree[tree[next].l].val-tree[tree[head].l].val)
		return query(tree[head].l,tree[next].l,l,mid,rank);
	if(rank<tree[tree[next].r].val-tree[tree[head].r].val)
		return query(tree[head].r,tree[next].r,mid+1,r,rank);
	return 0;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b+1,b+n+1);
	int size=unique(b+1,b+n+1)-b-1;
	root[0]=build(1,size);
	for(int i=1;i<=n;i++)
		root[i]=updata(root[i-1],1,size,lower_bound(b+1,b+size+1,a[i])-b);
	while(m--){
		cin>>x>>y;
		cout<<query(root[x-1],root[y],1,size,(y-x+1)/2)<<endl;
	}
	return 0;
}