#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=2e5,N2=5+24*N;
ll root[N2],lc[N2],rc[N2],st[N2],nd;
void bd(ll lik,ll l=1,ll r=N){
if(l==r)return;
lc[lik]=++nd;
rc[lik]=++nd;
bd(lc[lik],l,(l+r)/2);
bd(rc[lik],(l+r)/2+1,r);
}
void upd(ll pr,ll tr,ll id,ll l=1,ll r=N){
if(l==r){st[tr]=1+st[pr];return;}
ll md=(l+r)/2;
if(id<=md){
rc[tr]=rc[pr];
lc[tr]=++nd;
upd(lc[pr],lc[tr],id,l,md);
}else{
lc[tr]=lc[pr];
rc[tr]=++nd;
upd(rc[pr],rc[tr],id,md+1,r);
}
st[tr]=st[lc[tr]]+st[rc[tr]];
}
ll walk(ll pr,ll tr,ll x,ll l=1,ll r=N){
if(l==r)return l;
ll md=(l+r)/2;
ll rgt=st[rc[tr]]-st[rc[pr]];
if(rgt>=x)return walk(rc[pr],rc[tr],x,md+1,r);
else return walk(lc[pr],lc[tr],x-rgt,l,md);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
ll n,q;
cin>>n>>q;
root[0]=++nd;
bd(root[0]);
for(int i=1;i<=n;++i){
ll x;cin>>x;
root[i]=++nd;
upd(root[i-1],root[i],x);
}
while(q--){
ll l,r;cin>>l>>r;
ll L=1,R=N,A=L;
while(L<=R){
ll M=(L+R)/2;
if(walk(root[l-1],root[r],M)>=M){
A=M;
L=M+1;
}else
R=M-1;
}
cout<<A<<'\n';
}
}
