#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=2e5+10;
int a[N],n;
const int M=6e6;
int sm[M],lc[M],rc[M],lst=0;
int gnn(int ref=-1)
{
int cn=lst++;
sm[cn]=0;
if(ref!=-1)lc[cn]=lc[ref],rc[cn]=rc[ref];
return cn;
}
int build(int l=1,int r=n)
{
int v=gnn();
if(l==r)
return v;
int m=(l+r)>>1;
lc[v]=build(l,m);
rc[v]=build(m+1,r);
return v;
}
void set(int&v,int i,int l=1,int r=n)
{
if(i<l or r<i)return;
v=gnn(v);
if(l==r)
{
sm[v]=1;
return;
}
int m=(l+r)>>1;
set(lc[v],i,l,m);
set(rc[v],i,m+1,r);
sm[v]=sm[lc[v]]+sm[rc[v]];
}
int qry(int&v,int ql,int qr,int l=1,int r=n)
{
if(qr<l or r<ql)return 0;
if(ql<=l and r<=qr)
return sm[v];
int m=(l+r)>>1;
return qry(lc[v],ql,qr,l,m)+qry(rc[v],ql,qr,m+1,r);
}
vector<pair<int,int>> tp;
vector<int> ver;
bool check(int h,int l,int r)
{
int s=-1,e=tp.size();
while(s+1<e)
{
int m=(s+e)>>1;
if(tp[m].first>=h)
{
s=m;
}
else
{
e=m;
}
}
return qry(ver[s+1],l,r)>=h;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int q;
cin>>n>>q;
for(int i=1;i<=n;i++)
{
cin>>a[i];
tp.push_back({a[i],i});
}
sort(rbegin(tp),rend(tp));
ver.push_back(build());
for(auto [x,i]:tp)
{
// cout<<"x "<<x<<' '<<i<<endl;
ver.push_back(ver.back());
set(ver.back(),i);
}
while(q--)
{
int l,r;
cin>>l>>r;
int s=0,e=2e5+10;
while(s+1<e)
{
int m=(s+e)>>1;
if(check(m,l,r))
{
s=m;
}
else
{
e=m;
}
}
cout<<s<<endl;
}
}
