//P3567 [POI2014] KUR-Couriers

#include<bits/stdc++.h>
//#define lc(u) tr[u].ls
//#define rc(u) tr[u].rs
#define int unsigned int
using namespace std;
const int N=5e5+10;
int n,a[N],m;
int rt[N],idx;
struct node{
	int ls,rs,cnt;
}tr[N<<5];
inline void modify(int prev,int u,int pos,int l,int r){
	tr[u]=tr[prev];
	++tr[u].cnt; 
	if(l==r)
		return;
	int mid=l+r>>1;
	if(pos<=mid){
		tr[u].ls=++idx;
		modify(tr[prev].ls,tr[u].ls,pos,l,mid);
	}
	else{
		tr[u].rs=++idx;
		modify(tr[prev].rs,tr[u].rs,pos,mid+1,r);
	}
}
inline int query(int u,int ql,int qr,int l,int r){
	if(l>=ql&&r<=qr)
		return tr[u].cnt;
	if(tr[u].cnt==0)return 0;
	int mid=l+r>>1;
	int res=0;
	if(ql<=mid&&tr[u].ls)res+=query(tr[u].ls,ql,qr,l,mid);
	if(qr>mid&&tr[u].rs)res+=query(tr[u].rs,ql,qr,mid+1,r);
	return res;
}
int maxna,minna=1e9;
int q(int l,int r,int x){
	if(x<maxna)return query(rt[r],x+1,maxna,minna,maxna)-((l<=1)?0:query(rt[l-1],x+1,maxna,minna,maxna));
	else return 0;
}
namespace fastread {
	const int S=1<<16;
	char B[S+3],*H,*T;
	inline int gc() {
		if(H==T) T=(H=B)+fread(B,1,S,stdin);
		return (H==T)?EOF:*H++;
	}
	inline int read() {
		int x,ch;
		while((ch=gc())<48);
		x=ch^48;
		while((ch=gc())>47) x=(x<<3)+(x<<1)+(ch^48);
		return x;
	}
} using fastread::read;

namespace fastwrite {
	const int S=1<<16;
	int cnt;
	char B[S+3];
	inline void write(int x) {
		if(x>9) write(x/10);
		B[cnt++]=(x%10)|48;
		if(cnt == S){
			fwrite(B,1,S,stdout);
			cnt=0;
		} 
	}
	inline void space() {
		B[cnt++]=32;
		if(cnt == S){
			fwrite(B,1,S,stdout);
			cnt=0;
		} 
	}
	inline void endl() {
		B[cnt++]=10;
		if(cnt == S){
			fwrite(B,1,S,stdout);
			cnt=0;
		} 
	}
	inline void show() {
		fwrite(B,1,cnt,stdout);
		cnt=0;
	}
}using fastwrite::write;using fastwrite::space;using fastwrite::show;

int mx1,mx2,mx3,mx4,mx5,mx6;
int max(int x,int y){
	if(y-x>>31)return x;
	return y;
}
signed main(){
	n=read(),m=read();
	register int i;
	for(i=1;i+6<=n;i+=6){
		a[i]=read(),a[i+1]=read(),a[i+2]=read(),a[i+3]=read(),a[i+4]=read(),a[i+5]=read();
		mx6=max(mx6,a[i]),mx1=max(mx1,a[i+1]),mx2=max(a[i+2],mx2),mx3=max(mx3,a[i+3]),mx4=max(mx4,a[i+4]),mx5=max(a[i+5],mx5);
	}
	maxna=max(max(mx1,mx2),max(max(mx3,mx4),max(mx5,mx6)));
	for(;i<=n;++i)a[i]=read(),maxna=max(maxna,a[i]);
	minna=1;
	for(register int i=1;i<=n;++i){
		rt[i]=++idx;
		modify(rt[i-1],rt[i],a[i],minna,maxna);
	}
	int ll,bigger,rr,mid,l,r,len;
	while(m--){
		l=read(),r=read();
		ll=1,rr=maxna,len=r-l+1;
		while(ll<rr){
			mid=ll+rr>>1;
			bigger=q(l,r,mid);
			if(bigger>=len-bigger)ll=mid+1;
			else rr=mid;
		}
		(1-l>>31)?(bigger=query(rt[r],rr,rr,minna,maxna)-query(rt[l-1],rr,rr,minna,maxna)):(bigger=query(rt[r],rr,rr,minna,maxna));
		bigger<=len-bigger?write(0):write(rr);
		fastwrite::endl();
	}
	show();
	return 0;
}