#include<bits/stdc++.h>
#define pli pair<long long,long long>
using namespace std;
using ll=long long;
const ll maxN=3e5+5;
ll n, a[maxN],id[maxN],st[4*maxN];
void build(ll id, ll l, ll r)
{
if(l==r)
{
st[id]=0;
return;
}
ll mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
st[id]=st[id*2]+st[id*2+1];
}
void update(ll id, ll l, ll r, ll pos, ll val)
{
if(pos<l||pos>r) return;
if(l==r)
{
st[id]=val;
return;
}
ll mid=(l+r)/2;
update(id*2,l,mid,pos,val);
update(id*2+1,mid+1,r,pos,val);
st[id]=st[id*2]+st[id*2+1];
}
ll get(ll id, ll l, ll r, ll i, ll j)
{
if(r<i||j<l) return 0;
if(i<=l&&r<=j)
{
return st[id];
}
ll mid=(l+r)/2;
return get(id*2,l,mid,i,j)+get(id*2+1,mid+1,r,i,j);
}
bool lf(ll x, ll y)
{
return a[x]>a[y];
}
struct TQuery
{
ll l, r, mid, low, high;
}q[maxN];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int que;
cin >> n>> que;
for(int i=1;i<=n;i++) cin >> a[i],id[i]=i;
sort(id+1,id+n+1,lf);
//for(int i=1;i<=n;i++) cout << id[i]<<' ';
for(int i=1;i<=que;i++)
{
cin >> q[i].l >> q[i].r;
q[i].low=1;
q[i].high=q[i].r-q[i].l+1;
}
vector<pli> v;
while(true)
{
v.clear();
build(1,1,n);
for(int i=1;i<=que;i++)
{
if(q[i].low>q[i].high)
{
continue;
}
else
{
q[i].mid=(q[i].low+q[i].high)/2;
v.push_back({q[i].mid,i});
}
}
if(v.size()==0) break;
sort(v.begin(),v.end(),greater<pli>());
int j=1;
for(int i=0;i<v.size();i++)
{
while(a[id[j]]>=v[i].first)
{
update(1,1,n,id[j],1);
j++;
}
ll idx=v[i].second;
ll x=get(1,1,n,q[idx].l,q[idx].r);
if(x>=q[idx].mid) q[idx].low=q[idx].mid+1;
else q[idx].high=q[idx].mid-1;
}
}
for(int i=1;i<=que;i++)
{
cout << q[i].high<<'\n';
}
}
