#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
int n,m,l,r,k,h[500005],ctt,cnt,root[500005],mm,va,loc;
inline void writeT(long long x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) writeT(x/10);
    putchar(x%10+'0');return;
}
struct zyh{
	int lc,rc,t;
}tree[100000005];
int read() {
	int f = 1, k = 0;
	char c = getchar();
	while(c < '0' || c > '9'){
		c = getchar();
	}
	while( c >= '0' && c<= '9'){
		k = (k << 1) + (k << 3) + (c ^ 48);
		c = getchar();
	}
	return f * k;
	
}
int q(int x, int y, int o, int ql, int qr) {
    if (ql <= x && y <= qr) return tree[o].t;
    int mid = (x + y) >> 1, res = 0;
    if (ql <= mid) res += q(x, mid, tree[o].lc, ql, qr);
    if (qr > mid) res += q(mid + 1, y, tree[o].rc, ql, qr);
    return res;
}

void build(int l,int r,int o){//printf("%d %d %d\n",l,r,o);
	if(l==r)return;
	else{
		int mid=(l+r)>>1;
		tree[o].lc=++cnt;
		tree[o].rc=++cnt;
		build(l,mid,tree[o].lc);
		build(mid+1,r,tree[o].rc);
	}
}
void add(int l,int r,int o2,int o){
	if(l==r)tree[o].t=tree[o2].t+va;
	else{
		int mid=(l+r)>>1;
		if(loc<=mid){
			tree[o].lc=++cnt;
			tree[o].rc=tree[o2].rc;
			add(l,mid,tree[o2].lc,cnt);
			tree[o].t=tree[tree[o2].rc].t+tree[tree[o].lc].t;
		}
		else{
			tree[o].rc=++cnt;
			tree[o].lc=tree[o2].lc;
			add(mid+1,r,tree[o2].rc,cnt);
			tree[o].t=tree[tree[o2].lc].t+tree[tree[o].rc].t;
		}
	}
}
int a[500005], b[500005];
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)a[i]=b[i]=read();
	std::sort(b+1,b+n+1);
	ctt=unique(b+1,b+1+n)-(b+1);
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(b+1,b+1+ctt,a[i])-b;
	build(1,ctt,++cnt);root[0]=1;
	for(int i=1;i<=n;i++)root[i]=++cnt,loc=a[i],va=1,add(1,ctt,root[i-1],cnt);
	while (m--) {
    scanf("%lld%lld", &l, &r);
    k=((r-l)>>1)+1;
    int ql = 1, qr = ctt, ans;
    while (ql <= qr) {
        int mid = (ql + qr) >> 1;
        int count = q(1, ctt, root[r], 1, mid) - q(1, ctt, root[l - 1], 1, mid);
        if (count >= k) {
            ans = mid;
            qr = mid - 1;
        } else {
            ql = mid + 1;
        }
    }
    if(q(1, ctt, root[r], ans, ans) - q(1, ctt, root[l - 1], ans, ans)>((r-l+1)>>1))writeT(b[ans]),puts("");
    else puts("0");
}

}

啥快读快写都开了，还是T