#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
const int mod=1e9+7;
#define inf 1e9
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mkp make_pair
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
struct ask{
	int l,r,id;
	bool operator<(ask b){
		return l==b.l?(r==b.r?id<b.id:r>b.r):l<b.l;
	}
}q[maxn];
int n,m,Ans[maxn];
vector<int>v[maxn];
struct bit{
	int tr[maxn];
	inline void add(int x,int c){for(;x<=n;x+=x&(-x))tr[x]+=c;}
	inline void init(int x){for(;x;--x)add(x,1);}
	inline int qry(int x){int res=0;for(;x;x-=x&(-x))res+=tr[x];return res;}
}B;
struct seg{
	int tr[maxn<<2],laz[maxn<<2];
	inline void build(int h,int l,int r){
		tr[h]=-inf;if(l==r)return;
		int mid=(l+r)>>1;
		build(h<<1,l,mid),build(h<<1|1,mid+1,r);
	}
	inline void pushup(int h,int z){tr[h]+=z;laz[h]+=z;}
	inline void pushdown(int h){pushup(h<<1,laz[h]);pushup(h<<1|1,laz[h]);laz[h]=0;}
	inline void modify(int h,int l,int r,int x,int y,int z){
		if(l>y||r<x)return;
		if(l>=x&&r<=y)return void(pushup(h,z));
		pushdown(h);int mid=(l+r)>>1;
		modify(h<<1,l,mid,x,y,z);
		modify(h<<1|1,mid+1,r,x,y,z);
		tr[h]=max(tr[h<<1],tr[h<<1|1]);
	}
	inline void update(int h,int l,int r,int x,int y){
		if(l==r)return void(tr[h]=y);
		int mid=(l+r)>>1;pushdown(h);
		if(mid>=x)update(h<<1,l,mid,x,y);
		else update(h<<1|1,mid+1,r,x,y);
		tr[h]=max(tr[h<<1],tr[h<<1|1]);
	}
	inline int qry(int h,int l,int r,int w){
		if(l==r)return l;int mid=(l+r)>>1;pushdown(h);
		return tr[h<<1]>=w?qry(h<<1,l,mid,w):qry(h<<1|1,mid+1,r,w);
	}
}T;
struct seg2{
	pii tr[maxn<<2];
	inline void build(int h,int l,int r){
		tr[h]=mkp(-inf,0);if(l==r)return;
		int mid=(l+r)>>1;
		build(h<<1,l,mid),build(h<<1|1,mid+1,r);
	}
	inline void update(int h,int l,int r,int x,pii y){
		if(l==r)return void(tr[h]=y);
		int mid=(l+r)>>1;
		if(mid>=x)update(h<<1,l,mid,x,y);
		else update(h<<1|1,mid+1,r,x,y);
		tr[h]=max(tr[h<<1],tr[h<<1|1]);
	}
	inline pii qry(int h,int l,int r,int x,int y){
		if(l>y||r<x)return mkp(-inf,0);
		if(l>=x&&r<=y)return tr[h];
		int mid=(l+r)>>1;
		return max(qry(h<<1,l,mid,x,y),qry(h<<1|1,mid+1,r,x,y));
	}
}G;
set<pii>Sl,Sr;
inline void pushin(int i){
//	printf("in pushin i=%d\n",i);
	Sl.insert(mkp(q[i].l,i)),Sr.insert(mkp(q[i].r,i));
	T.update(1,1,m,i,B.qry(q[i].r)-B.qry(q[i].l-1));
//	printf("out pushin i=%d\n",i);
}
inline void del(int i){
//	printf("in del i=%d\n",i);
	auto it=Sl.erase(Sl.find(mkp(q[i].l,i)));
	int r=it==Sl.end()?m:(*it).se;
	it=Sr.erase(Sr.find(mkp(q[i].r,i)));
	int lim=it==Sr.begin()?0:(*--it).se;
	int id;pii tmp;//puts("ready to in loop");
	while(tmp=G.qry(1,1,m,i,r),tmp.fi>lim){
		id=-tmp.se;pushin(id);
		G.update(1,1,m,id,mkp(-inf,0));r=id;
	}T.update(1,1,m,i,-1);
//	printf("out del i=%d\n",i);
}
int main(){
	n=read(),m=read();int Mx=n;
	for(int i=1,x;i<=n;i++)x=read(),v[x].pb(i),Mx=max(Mx,x);
	for(int i=1;i<=m;i++)
		q[i].l=read(),q[i].r=read(),q[i].id=i;
	sort(q+1,q+1+m);B.init(n);
	T.build(1,1,m),G.build(1,1,m);
	for(int i=1,r=0;i<=m;i++)
		if(q[i].r>r)pushin(i),r=q[i].r;
		else G.update(1,1,m,i,mkp(q[i].r,-i));
	for(int i=Mx;~i;i--){
		for(auto x:v[i]){
			B.add(x,-1);
			if(!Sl.empty()){
				auto L=Sr.lower_bound(mkp(x,0));
				if(L==Sr.end())continue;
				auto R=Sl.lower_bound(mkp(x,inf));
				if(R==Sl.begin())continue;
				--R;T.modify(1,1,m,L->se,R->se,-1);
			}
		}while(T.tr[1]>=i){
			int pos=T.qry(1,1,m,i);
			del(pos);Ans[q[pos].id]=i;
		}//printf("over i=%d\n",i);
	}
	for(int i=1;i<=m;i++)
		printf("%d\n",Ans[i]);
	return 0;
}