RT，以下代码不开O2可AC，但开O2后几乎全RE。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 20000050
int id,lc[N],rt[N],val[N],s[N],rc[N],a[N],b[N],n,m;
int new_node(int p){
	++id;val[id]=val[p],lc[id]=lc[p],rc[id]=rc[p];return id;
}
void insert(int p,int &x,int l,int r,int pos){
	x=new_node(p);++val[x];
	if(l==r)return ;
	int mid=l+r>>1;
	if(pos<=mid)insert(lc[p],lc[x],l,mid,pos);
	else insert(rc[p],rc[x],mid+1,r,pos);
}
int find(int p,int q,int l,int r,int k){
	if(l==r)return l;
	int mid=l+r>>1,s=val[lc[p]]-val[lc[q]];
	if(s>=k)return find(lc[p],lc[q],l,mid,k);
	else if(val[rc[p]]-val[rc[q]]>=k) find(rc[p],rc[q],mid+1,r,k);
	else return 0;
}
void read(int &x){
	x=0;char ch=getchar();int w=0;
	while(ch>'9'||ch<'0')w^=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=getchar();
	if(w)x=-x;
}
void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar((x%10)+'0');
}
signed main(){
	read(n);read(m);for(int i=1;i<=n;i++)read(a[i]);
	for(int i=1;i<=n;i++)insert(rt[i-1],rt[i],1,n,a[i]);
	while(m--){
		int l,r;read(l);read(r);
		print(find(rt[r],rt[l-1],1,n,(r-l+3)/2));puts("");
	}
}