给一个长度为n的序列a。1≤a[i]≤n。
m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。

第一行两个数n，m。
第二行n个数，a[i]。
接下来m行，每行两个数l,r，表示询问[l,r]这个区间。

m行，每行对应一个答案。

/*by SilverN*/#include<iostream>#include<algorithm>#include<cstring>#include<cstdio>#include<cmath>using namespace std;const int mxn=500010;int read(){    int x=0,f=1;char ch=getchar();    while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}int n,m;struct node{    int lc,rc;    int sum;}t[mxn*20];int root[mxn];int nct=0;void update(int la,int v,int l,int r,int &rt){    rt=++nct;    t[rt]=t[la];    t[rt].sum++;    if(l==r)return;    int mid=(l+r)>>1;    if(v<=mid)update(t[la].lc,v,l,mid,t[rt].lc);    else update(t[la].rc,v,mid+1,r,t[rt].rc);    return;}int query(int L,int R){    int l=1,r=n;    int mid,la=root[L-1],y=root[R],tmp=(R-L+1)/2;    while(l!=r){        if(t[y].sum-t[la].sum<=tmp)return 0;        mid=(l+r)>>1;        if(t[t[y].lc].sum-t[t[la].lc].sum>tmp){            r=mid;            la=t[la].lc;            y=t[y].lc;        }        else if(t[t[y].rc].sum-t[t[la].rc].sum>tmp){        //else:不可能两边次数都多于(R-L+1)/2 所以可以二分            l=mid+1;            la=t[la].rc;            y=t[y].rc;        }        else return 0;    }    return l;}int main(){    n=read();m=read();    int i,j,x,y,l,r;    for(i=1;i<=n;i++){        x=read();        update(root[i-1],x,1,n,root[i]);    }    for(i=1;i<=m;i++){        x=read();y=read();        printf("%d\n",query(x,y));    }    return 0;}