#include<bits/stdc++.h>
using namespace std;
int a[200005];
int l[200005],r[200005];
int ans[200005];
const int INF=1<<28;
const int N=200000;
struct point{
	int x[2];
	int id;
	bool operator == (point y)const{
		return y.x[0]==x[0]&&y.x[1]==x[1];
	}
}p[200005],g[200005];
bool cmp1(point x,point y)
{
	return x.x[0]<y.x[0]||x.x[0]==y.x[0]&&x.x[1]<y.x[1];
}
bool cmp2(point x,point y)
{
	return x.x[1]<y.x[1]||x.x[1]==y.x[1]&&x.x[0]<y.x[0];
}
int _x;
namespace edge{
	int he[200005],to[200005],ne[200005],cnt;
	void link(int x,int y)
	{
		cnt++;
		to[cnt]=y;
		ne[cnt]=he[x];
		he[x]=cnt;
	}
}
namespace star{
	int he[200005],to[200005],ne[200005],cnt;
	void link(int x,int y)
	{
		cnt++;
		to[cnt]=y;
		ne[cnt]=he[x];
		he[x]=cnt;
	}
}
namespace KDT{
	struct node{
		int fl;
		int lx,rx,ly,ry,dep;
		int mx,tag;
		int ls,rs;
		void make(int _l,int _r,int _s,int _t,int _d){lx=_l;rx=_r;ly=_s;ry=_t;dep=_d;}
	}tr[2000005];
	void add_tag(int k,int val)
	{
		tr[k].mx+=val;
		tr[k].tag+=val;
	}
	void pushdown(int k)
	{
		if(tr[k].ls)add_tag(tr[k].ls,tr[k].tag);
		if(tr[k].rs)add_tag(tr[k].rs,tr[k].tag);
		tr[k].tag=0;
	}
	void pushup(int k)
	{
		tr[k].mx=max(tr[tr[k].ls].mx,tr[tr[k].rs].mx);
	}
	int tot;
	int build(int l,int r,int d)
	{
		int mid=(l+r)>>1,no=++tot;
		tr[no].dep=d;
		tr[no].fl=-1;
		if(l==r)
		{
			tr[no].make(p[l].x[0],p[l].x[0],p[l].x[1],p[l].x[1],d);
			tr[no].fl=l;
			return no;
		}
		if(d&1)
		{
			nth_element(p+l,p+mid,p+r+1,cmp1);
			tr[no].ls=build(l,mid,d+1);
			tr[no].rs=build(mid+1,r,d+1);
		}
		else
		{
			nth_element(p+l,p+mid,p+r+1,cmp2);
			tr[no].ls=build(l,mid,d+1);
			tr[no].rs=build(mid+1,r,d+1);
		}
		tr[no].lx=min(tr[tr[no].ls].lx,tr[tr[no].rs].lx);
		tr[no].rx=max(tr[tr[no].ls].rx,tr[tr[no].rs].rx);
		tr[no].ly=min(tr[tr[no].ls].ly,tr[tr[no].rs].ly);
		tr[no].ry=max(tr[tr[no].ls].ry,tr[tr[no].rs].ry);
		pushup(no);
		return no;
	}
	bool outof(int a,int b,int c,int d)
	{
		return (b<c)||(a>d);
	}
	void modify(int k,int lx,int rx,int ly,int ry,int v)
	{
		if(outof(tr[k].lx,tr[k].rx,lx,rx)||outof(tr[k].ly,tr[k].ry,ly,ry))return;
		if(lx<=tr[k].lx&&tr[k].rx<=rx&&ly<=tr[k].ly&&tr[k].ry<=ry)
		{
			add_tag(k,v);
			return;
		}
		pushdown(k);
		if(tr[k].ls)modify(tr[k].ls,lx,rx,ly,ry,v);
		if(tr[k].rs)modify(tr[k].rs,lx,rx,ly,ry,v);
		pushup(k);
	}
	bool search(int k)
	{
		if(tr[k].fl!=-1)
		{
			if(tr[k].mx>=_x)
			{
				for(int i=star::he[tr[k].fl];i;i=star::ne[i])
				{
					ans[star::to[i]]=_x;
				}
				tr[k].mx=-INF;
				return true;
			}
			return false;
		}
		pushdown(k);
		bool ret;
		if(tr[tr[k].ls].mx>=tr[tr[k].rs].mx)
		{
			ret=search(tr[k].ls);
		}
		else
		{
			ret=search(tr[k].rs);
		}
		pushup(k);
		return ret;
	}
}
int main()
{
	int n,m,q=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		edge::link(a[i],i);
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&l[i],&r[i]);
		g[i]={{l[i],r[i]},i};
	}
	sort(g+1,g+1+m,cmp1);
	for(int i=1;i<=m;i++)
	{
		if(!(g[i]==g[i-1]))
		{
			q++;
			p[q]={{l[i],r[i]},q};
		}
		star::link(q,i);
	}
	int rt=KDT::build(1,q,1);
	for(int i=1;i<=n;i++)KDT::modify(rt,1,i,i,n,1);
	_x=N+1;
	while(_x>=0)
	{
		for(int i=edge::he[_x];i;i=edge::ne[i])
		{
			int j=edge::to[i];
			KDT::modify(rt,1,j,j,n,-1);
		}
		while(KDT::search(rt));
		_x--;
	}
	for(int i=1;i<=m;i++)
	{
		printf("%d\n",ans[i]);
	}
	return 0;
}