#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,q,a[N],ans[N],l[N],x[N],y[N],r[N],m[N],tree[N];
vector <int> v[N],que[N];
void update(int idx,int val){
for (int i=idx; i<N; i+=i&(-i)) {
tree[i]+=val;
}
}
int get(int idx) {
int ans=0;
for (int i=idx; i>0; i-=i&(-i)) {
ans+=tree[i];
}
return ans;
}
int main() {
cin>>n>>q;
for (int i=1; i<=n; i++) {
cin>>a[i];
v[a[i]].push_back(i);
}
for (int i=1; i<=q; i++){
cin>>x[i]>>y[i];
l[i]=1; r[i]=200000; m[i]=(l[i]+r[i])/2;
}
while(true){
int check=0;
for (int i=1; i<=q; i++){
if (l[i]>r[i]) continue;
//cout<<l[i]<<" "<<r[i]<<endl;
check=1;
que[m[i]].push_back(i);
}
if(!check) break;
for (int h=2e5; h>0; h--){
for (int j:v[h]) {
update(j, 1);
// cout<<h<<" "<<j<<" -------- > "<<1<<endl;
}
for (int j:que[h]){
if(get(y[j])-get(x[j]-1)>=h){ // get(x[j], y[j])
ans[j]=m[j]; l[j]=m[j]+1;
}
else r[j]=m[j]-1;
m[j] = (l[j]+r[j])/2;
}
}
for (int i=1; i<=2e5; i++) {
for (int j:v[i]) {
update(j, -1);
}
que[i].clear();
}
}
for (int i=1; i<=q; i++) cout<<ans[i]<<'\n';
}
