记录编号	483304	评测结果	AAAAAAAAAAAAAAA
题目名称	[POI 2014] 快递员	最终得分	100
用户昵称	AAAAAAAAAA	是否通过	通过
代码语言	C++	运行时间	1.383 s
提交时间	2018-01-16 09:43:41	内存使用	116.70 MiB

#include<bits/stdc++.h>
#define MAXN 500010
#define lc(x) t[x].l
#define rc(x) t[x].r
namespace IO{
	char buf[1<<15],*fs,*ft;
	inline char gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int qr(){
		int x=0,rev=0,ch=gc();
		while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=gc();}
		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();}
		return rev?-x:x;}
}using namespace IO;
using namespace std;
struct Note{
	int l,r,v;
}t[MAXN*20];
int N,M,root[MAXN],tot;
void Insert(int p,int l,int r,int &rt,int last){
	rt=++tot;t[rt]=t[last];t[rt].v++;
	if(l==r)return;
	int mid=l+r>>1;
	if(p<=mid)Insert(p,l,mid,lc(rt),lc(last));
	else Insert(p,mid+1,r,rc(rt),rc(last));
}
int Query(int a,int b,int l,int r,int k){
	if(l==r)return l;
	int mid=l+r>>1;
	if(t[lc(b)].v-t[lc(a)].v>k)return Query(lc(a),lc(b),l,mid,k);
	else if(t[rc(b)].v-t[rc(a)].v>k)return Query(rc(a),rc(b),mid+1,r,k);
	else return 0;
}
int x,y;
int main(){
	freopen("kur.in","r",stdin);
	freopen("kur.out","w",stdout);
	N=qr();M=qr();
	for(int i=1;i<=N;i++)x=qr(),Insert(x,1,N,root[i],root[i-1]);
	for(int i=1;i<=M;i++){
		x=qr();y=qr();
		printf("%d\n",Query(root[x-1],root[y],1,N,(y-x+1)>>1));
	}
	return 0;
}