bool M1;
#define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<" MB\n"
#define look_time cerr<<(clock()-Time)*1.0/CLOCKS_PER_SEC<<'\n'
#include <cstdio>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <cstring>
#include <array>
#include <algorithm>
#include <queue>
#include <vector>
#include <bitset>
#include <ctime>
#include <cstdlib>
#include <random>
#include <set>
#include <ctime>
#include <map>
#include <stack>
#include <unordered_map>
#include <assert.h>
#define i128 __int128
#define ll long long
#define uint unsigned
#define ull unsigned long long
#define fo(a,b,c) for(ll a=b;a<=c;++a)
#define re(a,b,c) for(ll a=b;a>=c;--a)
#define pii pair<ll,ll>
#define pdd pair<db,db>
#define fi first
#define pb push_back
#define se second
#define ite set<pii> ::iterator
using namespace std;
const ll mod=998244353;
inline ll gi()
{
	ll x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x = (x<<1) + (x<<3) + (ch^48);
		ch = getchar();
	}
	return x * f;
}
ll _=1;
const ll inf=2e17+5,iinf=2e9;
const ll N=500005;
struct sgt
{
	pii mx[N];
	ll tag[N];
	void wk(ll rt,ll val)
	{
		tag[rt]+=val;
		mx[rt].fi+=val;
	}
	void pd(ll rt)
	{
		if(tag[rt]==0) return;
		wk(rt*2,tag[rt]);
		wk(rt*2+1,tag[rt]);
		tag[rt]=0;
	}
	void bt(ll rt,ll l,ll r,ll tg)
	{
		if(l==r)
		{
			if(tg) mx[rt]={-inf,-l};
			else mx[rt]={-inf,l};
			return;
		}
		ll mid=(l+r)/2;
		bt(rt*2,l,mid,tg);
		bt(rt*2+1,mid+1,r,tg);
		mx[rt]=max(mx[rt*2],mx[rt*2+1]);
	}
	void ud(ll rt,ll l,ll r,ll L,ll R,ll val)
	{
		if(L<=l&&r<=R)
		{
			wk(rt,val);
			return;
		}
		pd(rt);
		ll mid=(l+r)/2;
		if(L<=mid) ud(rt*2,l,mid,L,R,val);
		if(R>mid) ud(rt*2+1,mid+1,r,L,R,val);
		mx[rt]=max(mx[rt*2],mx[rt*2+1]);
	}
	void cg(ll rt,ll l,ll r,ll pos,pii val)
	{
		if(l==r)
		{
			mx[rt]=val;
			return;
		}
		pd(rt);
		ll mid=(l+r)/2;
		if(pos<=mid) cg(rt*2,l,mid,pos,val);
		else cg(rt*2+1,mid+1,r,pos,val);
		mx[rt]=max(mx[rt*2],mx[rt*2+1]);
	}
	pii qr(ll rt,ll l,ll r,ll L,ll R)
	{
		if(L<=l&&r<=R) return mx[rt];
		pd(rt);
		ll mid=(l+r)/2;
		if(R<=mid) return qr(rt*2,l,mid,L,R);
		if(L>mid) return qr(rt*2+1,mid+1,r,L,R);
		return max(qr(rt*2,l,mid,L,R),qr(rt*2+1,mid+1,r,L,R));
	}
}t1,t2;
ll n,q;
ll a[N];
struct IO
{
	ll l,r,id;
}e[N];
bool cmp(IO za,IO zb)
{
	if(za.l==zb.l) return za.r>zb.r;
	return za.l<zb.l;
}
vector<ll> g[N];
ll bit[N];
ll lb(ll x)
{
	return x&-x;
}
void add(ll x,ll y)
{
	for(;x<=n;x+=lb(x)) bit[x]+=y;
}
ll qr(ll x)
{
	ll res=0;
	for(;x;x-=lb(x)) res+=bit[x];
	return res;
}
set<pii> sl,sr;
void ins(ll x)
{
	t1.cg(1,1,q,x,{qr(e[x].r)-qr(e[x].l-1),x});
	sl.insert({e[x].l,x});
	sr.insert({e[x].r,x});
}
void del(ll x)
{
	t1.cg(1,1,q,x,{-inf,x});
	sl.erase({e[x].l,x});
	ite it=sl.lower_bound({e[x].l,x});
	ll nxt=q;
	if(it!=sl.end()) nxt=it->se;
	sr.erase({e[x].r,x});
	it=sr.lower_bound({e[x].r,x});
	ll lim=0;
	if(it!=sr.begin())
	{
		it--;
		lim=it->fi;
	}
	
	while(1)
	{
		pii p=t2.qr(1,1,q,x,nxt);
		if(p.fi<=lim)break;
		ll zid=-p.se;
		nxt=zid;
		ins(zid);
		t2.cg(1,1,q,zid,{-inf,-zid});
	}
}
ll ans[N];
void sol()
{
	n=gi(),q=gi();
	fo(i,1,n) a[i]=gi();
	fo(i,1,n)
	{
		a[i]=min(a[i],n);
		g[a[i]].pb(i);
		add(i,1);
	}
	fo(i,1,q)
	{
		e[i].l=gi(),e[i].r=gi();
		e[i].id=i;
	}
	sort(e+1,e+1+q,cmp);
	t1.bt(1,1,q,0);
	t2.bt(1,1,q,1);
	ll zmx=0;
	fo(i,1,q)
	{
		if(zmx<e[i].r) ins(i);
		else
		{
			t2.cg(1,1,q,i,{e[i].r,-i});
		}
		zmx=max(zmx,e[i].r);
	}
	re(i,n,0)
	{
		for(ll x:g[i])
		{
			add(x,-1);
			if(sl.size())
			{
				ite it2=sl.lower_bound({x,inf}),it1=sr.lower_bound({x,-inf});
				if(it1!=sr.end()&&it2!=sl.begin())
				{
					it2--;
					t1.ud(1,1,q,it1->se,it2->se,-1);
				}
			}
		}
		while(1)
		{
			if(t1.mx[1].fi>=i)
			{
				ans[e[t1.mx[1].se].id]=i;
				del(t1.mx[1].se);
			}
			else break;
		}
	}
	fo(i,1,q) cout<<ans[i]<<'\n';
}
bool M2;
int main()
{
	int Time=clock();
	look_memory;
//	_=gi();
	while(_--)
	{
		sol();
		printf("\n");
	}
	look_time;
	return 0;
}