#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e5;
int tab[N+10];
int srt[N+10];
int l[N+10],r[N+10];
int bg[N+10],en[N+10];
int fen[N+10];
int lsb(int x) { return x&(-x); }
void add(int x,int n)
{
for(;x<=n;x+=lsb(x))
fen[x]++;
return;
}
int read(int x)
{
int ans=0;
for(;x>0;x-=lsb(x))
ans+=fen[x];
return ans;
}
int read(int ll,int rr)
{
return read(rr)-read(ll-1);
}
void bs(int n,int q)
{
int active=q;
vector<pair<int,int>> mid;
while(active>0)
{
for(int i=1;i<=n;i++)
{
if(bg[i]<en[i])
mid.emplace_back((bg[i]+en[i]+1)/2,i);
}
sort(mid.begin(),mid.end());
for(int i=0;i<=n;i++)
fen[i]=0;
for(int i=1;i<=n;i++)
{
while(!mid.empty() && mid.back().fi>tab[srt[i]])
{
auto [m,x]=mid.back();
mid.pop_back();
if(read(l[x],r[x])>=m)
bg[x]=m;
else
en[x]=m-1;
if(bg[x]>=en[x])
active--;
}
add(srt[i],n);
}
while(!mid.empty())
{
auto [m,x]=mid.back();
mid.pop_back();
bg[x]=m;
if(bg[x]>=en[x])
active--;
}
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++)
{
cin>>tab[i];
srt[i]=i;
}
sort(srt+1,srt+n+1,[](int a,int b){ return tab[a]>tab[b]; });
for(int i=1;i<=q;i++)
{
cin>>l[i]>>r[i];
bg[i]=0;
en[i]=n;
}
bs(n,q);
for(int i=1;i<=q;i++)
cout<<bg[i]<<"\n";
return 0;
}
