#include "bits/stdc++.h"
#define mod 1000000007
#define inf 4000000000000000000
using namespace std;
#define int long long
const int maxn=200'001;
const int N=1<<(17+1);
vector<int>pos[maxn], buc[maxn];
int seg[4*N];
void upd(int i){
i=i+N-1;
seg[i]=1;
while(i/=2) seg[i]=seg[2*i]+seg[2*i+1];
}
int query(int ql, int qr, int i=1, int l=1, int r=N){
if(ql>r or qr<l) return 0;
if(ql<=l and qr>=r) return seg[i];
int m=(l+r)/2;
return query(ql, qr, 2*i, l, m)+query(ql, qr, 2*i+1, m+1, r);
}
vector<int> p(maxn), l(maxn), r(maxn);
vector<int> la(maxn), ra(maxn), ans(maxn);
signed main(){
int n, q; cin>>n>>q;
for(int i=1; i<=n; i++){cin>>p[i]; pos[p[i]].push_back(i);}
for(int i=1; i<=q; i++){
cin>>l[i]>>r[i]; la[i]=1; ra[i]=n;
buc[(1+n)/2].push_back(i);
}
for(int _=0; _<19; _++){
memset(seg, 0, sizeof seg);
for(int i=maxn-1; i>=1; i--){
for(int j : pos[i]) upd(j);
for(int j : buc[i]){
int k=query(l[j], r[j]);
if(k>=i){ans[j]=i; la[j]=i+1;}
else ra[j]=i-1;
if(ra[j]>=la[j])buc[(ra[j]+la[j])/2].push_back(j);
}
buc[i].clear();
}
}
for(int i=1; i<=q; i++) cout<<ans[i]<<'\n';
}
