#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=2e5+10,LG=20;
int a[N],n,fen[N],l[N],r[N],bl[N],br[N];
vector<int> cur[N],oc[N];
void add(int p,int v=1)
{
while(p<N)
{
fen[p]+=v;
p+=(p&-p);
}
}
int get(int x)
{
int ans=0;
while(x)
{
ans+=fen[x];
x-=(x&-x);
}
return ans;
}
int get(int l,int r)
{
return get(r)-get(l-1);
}
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];
oc[a[i]].push_back(i);
}
for(int i=0;i<q;i++)
{
cin>>l[i]>>r[i];
bl[i]=0,br[i]=2e5+1;
cur[(bl[i]+br[i])/2].push_back(i);
}
for(int j=0;j<LG;j++)
{
for(int i=N-1;i>=0;i--)
{
for(auto&ind:oc[i])
{
add(ind);
}
for(auto&id:cur[i])
{
if(get(l[id],r[id])>=i)
{
bl[id]=i;
}
else
{
br[id]=i;
}
if(bl[id]+1<br[id])
cur[(bl[id]+br[id])/2].push_back(id);
}
cur[i].clear();
}
for(int i=0;i<N;i++)fen[i]=0;
}
for(int i=0;i<q;i++)
{
cout<<bl[i]<<endl;
}
}
