可持久化线段树
裸可持久化线段树，把区间第K大的rank改成num即可……（往儿子走的时候不减少）
苦逼的我……MLE了一次（N*30），RE了一次（N*10）……数组大小不会开……
最后开成N*20的过了
/**************************************************************
Problem: 3524
User: Tunix
Language: C++
Result: Accepted
Time:5752 ms
Memory:120416 kb
****************************************************************/ //BZOJ 3524
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std; int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>'') {if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<='') {v=v*+ch-''; ch=getchar();}
return v*=sign;
}
/*******************tamplate********************/
const int N=;
struct Tree{
int cnt,l,r;
}t[N*];
int root[N],n,m,cnt;
#define mid (l+r>>1)
void update(int &o,int l,int r,int pos){
t[++cnt]=t[o]; o=cnt; ++t[o].cnt;
if (l==r) return;
if (pos<=mid) update(t[o].l,l,mid,pos);
else update(t[o].r,mid+,r,pos);
}
int query(int i,int j,int num){
i=root[i],j=root[j];
int l=,r=n;
while(l!=r){
if (t[t[j].l].cnt-t[t[i].l].cnt>num)
r=mid,j=t[j].l,i=t[i].l;
else if (t[t[j].r].cnt-t[t[i].r].cnt>num)
l=mid+,j=t[j].r,i=t[i].r;
else return ;
}
return l;
}
#undef mid
int main(){
n=getint(),m=getint();
F(i,,n){
root[i]=root[i-];
update(root[i],,n,getint());
} F(i,,m){
int l=getint(),r=getint();
printf("%d\n",query(l-,r,(r-l+)>>));
}
return ;
}