#include<bits/stdc++.h>
using namespace std;
const int N=500005,inf=1e9;
int n,q,a[N],bz[N],ans[N],mxx,maxx[N],mxid[N];
struct node{int l,r,id;}b[N];
vector<int>v[N];
bool cmp(node x,node y){return x.l==y.l?(x.r>y.r):(x.l<y.l);}
struct BIT{
	int tr[N];
	void add(int x,int v){for (int i=x;i<=n;i+=(i&(-i)))tr[i]+=v;}
	int query(int x){int s=0;for (int i=x;i;i-=(i&(-i)))s+=tr[i];return s;}
	int qry(int l,int r){return query(r)-query(l-1);}
}t1;
struct sgt1{
	int mx[N<<2],id[N<<2],tag[N<<2];
	void pushup(int x){
		if (mx[x<<1]>mx[x<<1|1]){
			mx[x]=mx[x<<1];
			id[x]=id[x<<1];
		}
		else{
			mx[x]=mx[x<<1|1];
			id[x]=id[x<<1|1];
		}
	}
	void pushdown(int x){
		if (tag[x]!=0){
			mx[x<<1]+=tag[x];
			mx[x<<1|1]+=tag[x];
			tag[x<<1]+=tag[x];
			tag[x<<1|1]+=tag[x];
			tag[x]=0;
		}
	}
	void build(int l,int r,int x){
		if (l==r){
			if (bz[l])mx[x]=t1.qry(b[l].l,b[l].r);
			else mx[x]=-inf;
			id[x]=l;
			return;
		}
		int mid=(l+r)>>1;
		build(l,mid,x<<1),build(mid+1,r,x<<1|1);
		pushup(x);
	}
	void modify1(int x,int l,int r,int L,int R,int v){
		if (r<L||l>R)return;
		if (L<=l&&r<=R){mx[x]+=v,tag[x]+=v;return;}
		pushdown(x);
		int mid=(l+r)>>1;
		modify1(x<<1,l,mid,L,R,v),modify1(x<<1|1,mid+1,r,L,R,v);
		pushup(x);
	}
	void modify2(int x,int l,int r,int k,bool ck){
		if (l==r){mx[x]=ck?(-inf):(t1.qry(b[l].l,b[l].r));return;}
		pushdown(x);
		int mid=(l+r)>>1;
		if (k<=mid)modify2(x<<1,l,mid,k,ck);
		else modify2(x<<1|1,mid+1,r,k,ck);
		pushup(x);
	}
}t2;
struct Triple{
	int L,R,id;
};
struct Node{
	int x,id;
	friend bool operator<(Node x,Node y){
		return x.x<y.x;
	}
};
set<Node>e[N]; 
set<Node>s1,s2;
struct sgt2{
	int mx[N<<2],id[N<<2],idd[N<<2];
	void pushup(int x){
		if (mx[x<<1]>mx[x<<1|1]){
			mx[x]=mx[x<<1];
			id[x]=id[x<<1];
			idd[x]=idd[x<<1];
		}
		else if (mx[x<<1]<mx[x<<1|1]){
			mx[x]=mx[x<<1|1];
			id[x]=id[x<<1|1];
			idd[x]=idd[x<<1|1];
		}
		else{
			if (id[x<<1]<id[x<<1|1]){
				mx[x]=mx[x<<1];
				id[x]=id[x<<1];
				idd[x]=idd[x<<1];
			}
			else{
				mx[x]=mx[x<<1|1];
				id[x]=id[x<<1|1];
				idd[x]=idd[x<<1|1];
			}
		}
	}
	void build(int l,int r,int x){
		if (l==r){mx[x]=maxx[l],id[x]=l,idd[x]=mxid[l];return;}
		int mid=(l+r)>>1;
		build(l,mid,x<<1),build(mid+1,r,x<<1|1);
		pushup(x);
	}
	Triple query(int x,int l,int r,int L,int R){
		if (r<L||l>R)return (Triple){0,0,0};
		if (L<=l&&r<=R)return (Triple){id[x],mx[x],idd[x]};
		int mid=(l+r)>>1;
		Triple s1=query(x<<1,l,mid,L,R),s2=query(x<<1|1,mid+1,r,L,R);
		if (s1.R!=s2.R)return s1.R>s2.R?s1:s2;
		return s1;
	}
	void modify(int x,int l,int r,int k){
		if (l==r){
			if (e[l].empty())mx[x]=0,id[x]=0,idd[x]=0;
			else{
				Node u=(*e[l].begin());
				mx[x]=-u.x;
				id[x]=l;
				idd[x]=u.id;
			}
			return;
		}
		int mid=(l+r)>>1;
		if (k<=mid)modify(x<<1,l,mid,k);
		else modify(x<<1|1,mid+1,r,k);
		pushup(x);
	}
}t3; 
int main(){
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		v[a[i]].push_back(i);
		t1.add(i,1);
		mxx=max(mxx,a[i]);
	}
	for (int i=1;i<=q;++i)scanf("%d%d",&b[i].l,&b[i].r),b[i].id=i;
	sort(b+1,b+q+1,cmp);
	for (int i=1;i<=q;++i){
		e[b[i].l].insert((Node){-b[i].r,i}); 
	}
	for (int i=1;i<=n;++i){
		if (!e[i].empty()){
			maxx[i]=-(*e[i].begin()).x;
			mxid[i]=(*e[i].begin()).id;
		}
	}
	t3.build(1,n,1);
	int o=0;
	for (int i=1;i<=q;++i){
		if (b[i].r>o){
			o=b[i].r;
			bz[i]=1;
			s1.insert((Node){-b[i].l,i});
			s2.insert((Node){b[i].r,i});
		}
	}
	t2.build(1,q,1);
	for (int i=mxx+1;i>=0;--i){
		for (int j:v[i]){
			t1.add(j,-1);
			int L,R;
			if (s1.lower_bound((Node){-j,0})!=s1.end())R=(*s1.lower_bound((Node){-j,0})).id;
			else R=-1;
			if (s2.lower_bound((Node){j,0})!=s2.end())L=(*s2.lower_bound((Node){j,0})).id;
			else L=-1;
			if (L!=-1&&R!=-1)t2.modify1(1,1,q,L,R,-1);
		}
		while (t2.mx[1]>=i){
			int x=t2.id[1];
			ans[b[x].id]=i;
			t2.modify2(1,1,q,x,1);
			e[b[x].l].erase((Node){-b[x].r,x});
			t3.modify(1,1,n,b[x].l);
			bz[x]=2;
			int las,nex;
			if (s1.lower_bound((Node){1-b[x].l,0})!=s1.end())las=(*s1.lower_bound((Node){1-b[x].l,0})).id;
			else las=0;
			if (s2.lower_bound((Node){b[x].r+1,0})!=s2.end())nex=(*s2.lower_bound((Node){b[x].r+1,0})).id;
			else nex=0;
			s1.erase(s1.lower_bound((Node){-b[x].l,0}));
			s2.erase(s2.lower_bound((Node){b[x].r,0}));
			int L=b[x].l,R=(nex?(b[nex].l-1):n),lim=(las?(b[las].r+1):1);
			while (L<=R){
				Triple u=t3.query(1,1,n,L,R);
				if (u.id==0||u.R<lim)break;
				bz[u.id]=1;
				s1.insert((Node){-u.L,u.id});
				s2.insert((Node){u.R,u.id});
				t2.modify2(1,1,q,u.id,0);
				R=u.L-1;
			}
		}
	}
	for (int i=1;i<=q;++i)printf("%d\n",ans[i]);
}