#include<iostream> #include<cstdio> using namespace std; struct node{ int l,r,sum; }node[10000000]; int n,m,root[500010],size; void update(int pre,int &k,int l,int r,int v){ k=++size; node[k].sum=node[pre].sum+1; if(l==r)return; node[k].l=node[pre].l;node[k].r=node[pre].r; int mid=(l+r)>>1; if(v<=mid)update(node[pre].l,node[k].l,l,mid,v); else update(node[pre].r,node[k].r,mid+1,r,v); } int ask(int L,int R) { int l=1,r=n,mid,x,y,tmp=(R-L+1)>>1; x=root[L-1];y=root[R]; while(l!=r) { if(node[y].sum-node[x].sum<=tmp)return 0; mid=(l+r)>>1; if(node[node[y].l].sum-node[node[x].l].sum>tmp) {r=mid;x=node[x].l;y=node[y].l;} else if(node[node[y].r].sum-node[node[x].r].sum>tmp) {l=mid+1;x=node[x].r;y=node[y].r;} else return 0; } return l; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ int x;scanf("%d",&x); update(root[i-1],root[i],1,n,x); } for(int i=1;i<=m;i++){ int l,r;scanf("%d%d",&l,&r); printf("%d\n",ask(l,r)); } return 0; }