#include<bits/stdc++.h>
using namespace std;
const int N=5e6+10;
const int M=2e5+10;
struct node{
int l,r;
long long val;
}s[N];
vector<int> pos[M],df;
int arr[M],cnt=1,root[M];
int clone(int idx){s[++cnt]=s[idx]; return cnt;}
int build(int l,int r,int idx){
if(l==r){
s[idx]={0,0,0};
return idx;
}
int m=(l+r)/2;
s[idx].l=build(l,m,++cnt);
s[idx].r=build(m+1,r,++cnt);
s[idx].val=s[s[idx].l].val+s[s[idx].r].val;
return idx;
}
int update(int l,int r,int idx,int a,int b){
int now=clone(idx);
if(l==r){
s[now].val=b;
return now;
}
int m=(l+r)/2;
if(a<=m) s[now].l=update(l,m,s[idx].l,a,b);
else s[now].r=update(m+1,r,s[idx].r,a,b);
s[now].val=s[s[now].l].val+s[s[now].r].val;
return now;
}
int query(int l,int r,int idx,int a,int b){
if(a>r || b<l) return 0;
if(a<=l && b>=r) return s[idx].val;
int m=(l+r)/2;
return query(l,m,s[idx].l,a,b)+query(m+1,r,s[idx].r,a,b);
}
int main(){
int n,q;
cin>>n >>q;
for(int i=1;i<=n;i++){
cin>>arr[i];
pos[arr[i]].push_back(i);
df.push_back(arr[i]);
}
sort(df.begin(),df.end());
df.erase(unique(df.begin(),df.end()),df.end());
int rt=build(1,n,1);
reverse(df.begin(),df.end());
for(int i=0;i<df.size();i++){
//put df[i] in to the segment tree then update root[i] be the segment tree version i
for(auto ind:pos[df[i]]){
rt=update(1,n,rt,ind,1);
//cout<<"update" <<df[i] <<" " <<ind <<"\n";
}
root[i]=rt;
}
// for(int i=0;i<df.size();i++){
// for(int j=1;j<=n;j++){
// cout<<query(1,n,root[i],j,j) <<" ";
// }
// cout<<"\n";
// }
int sz=df.size();
while(q--){
int a,b;
cin>>a >>b;
int l=0,r=2e5;
while(l<r){
int mid=(l+r+1)/2;
int indl=0,indr=sz-1;
if(mid>df[0]){
r=mid-1;
continue;
}
while(indl<indr){
int indm=(indl+indr+1)/2;
if(df[indm]>=mid) indl=indm;
else indr=indm-1;
}
int ind=indl;
int fd=query(1,n,root[ind],a,b);
//cout<<mid <<" " <<fd <<"\n";
if(fd>=mid) l=mid;
else r=mid-1;
}
cout<<l <<"\n";
}
}
