思路：

按权值建一棵主席树

（但是这好像不是正解 空间复杂度是不对的…….）

//By SiriusRen#include 
     
      #include 
      
       #include 
       
        using namespace std;#define N 555555int n,m,cnt,root[N],a[N],xx,yy;struct Tree{
    int l,r,num;}tree[N*20];void push_up(int pos){tree[pos].num=tree[tree[pos].l].num+tree[tree[pos].r].num;}int build(int l,int r){    int pos=++cnt;    if(l==r){
    return pos;}    int mid=(l+r)>>1;    tree[pos].l=build(l,mid),tree[pos].r=build(mid+1,r);    return pos;}int insert(int o,int l,int r,int num){    int pos=++cnt;tree[pos]=tree[o];    if(l==r){tree[pos].num++;return pos;}    int mid=(l+r)>>1;    if(num<=mid)tree[pos].l=insert(tree[o].l,l,mid,num);    else tree[pos].r=insert(tree[o].r,mid+1,r,num);    push_up(pos);    return pos;}int query(int o,int v,int l,int r,int wei){    if(tree[o].num-tree[v].num<=wei)return 0;    if(l==r)return l;    int mid=(l+r)>>1;    if(tree[tree[o].l].num-tree[tree[v].l].num>wei)        return query(tree[o].l,tree[v].l,l,mid,wei);    else return query(tree[o].r,tree[v].r,mid+1,r,wei);}int main(){    scanf("%d%d",&n,&m);    root[0]=build(1,n);    for(int i=1;i<=n;i++)scanf("%d",&a[i]),root[i]=insert(root[i-1],1,n,a[i]);    for(int i=1;i<=m;i++){        scanf("%d%d",&xx,&yy);        printf("%d\n",query(root[yy],root[xx-1],1,n,(yy-xx+1)/2));    }}