// what is matter? never mind.
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 500005
#define inf 0x3f3f3f3f

int n,m,a[maxn],res[maxn],mx;
struct qry{
	int l,r,id;
	bool operator <(const qry&b)const{return l<b.l||(l==b.l&&r>b.r);}
}q[maxn];

struct bit{
	int tr[maxn];
	void U(int x,int y){for(;x<=n;x+=x&-x)tr[x]+=y;}
	int Q(int x){int s=0;for(;x;x^=x&-x)s+=tr[x];return s;}
	int Q(int l,int r){return Q(r)-Q(l-1);}
}tr;

struct segt{
	pii t[maxn<<2]; int tag[maxn<<2];
	void build(int p,int l,int r,bool bo){
		t[p]=mkp(-inf,bo?r:-l);
		if(l==r)return;
		int mid=l+r>>1;
		build(p<<1,l,mid,bo),build(p<<1|1,mid+1,r,bo); 
	}
	void up(int p){t[p]=max(t[p<<1],t[p<<1|1]);}
	void pt(int p,int v){tag[p]+=v,t[p].fi+=v;}
	void down(int p){if(tag[p])pt(p<<1,tag[p]),pt(p<<1|1,tag[p]),tag[p]=0;}
	void add(int p,int l,int r,int nl,int nr,int v){
		if(l>=nl&&r<=nr)return pt(p,v);
		int mid=l+r>>1;down(p);
		if(nl<=mid)add(p<<1,l,mid,nl,nr,v);
		if(nr>mid)add(p<<1|1,mid+1,r,nl,nr,v);up(p);
	}
	void upd(int p,int l,int r,int x,pii y){
		if(l==r)return tag[p]=0,t[p]=y,void();
		int mid=l+r>>1;down(p);
		x<=mid?upd(p<<1,l,mid,x,y):upd(p<<1|1,mid+1,r,x,y);up(p);
	}
	pii ask(int p,int l,int r,int ql,int qr){
		if(l>=ql&&r<=qr)return t[p];
		int mid=l+r>>1;down(p);pii res=mkp(-inf,-inf);
		if(ql<=mid)res=max(res,ask(p<<1,l,mid,ql,qr));
		if(qr>mid)res=max(res,ask(p<<1|1,mid+1,r,ql,qr));return res; 
	}
}T,T2;
set<pii>sl,sr;

void push(int i){
	sl.insert(mkp(q[i].l,i)),sr.insert(mkp(q[i].r,i));
	T.upd(1,1,m,i,mkp(tr.Q(q[i].l,q[i].r),i)); 
}
void del(int i){
	T.upd(1,1,m,i,mkp(-inf,i));
	sl.erase(mkp(q[i].l,i));
	auto it=sl.lower_bound(mkp(q[i].l,i));
	int r=(it==sl.end()?m:it->se);
	sr.erase(mkp(q[i].r,i));
	it=sr.lower_bound(mkp(q[i].r,i));
	int tmp=(it==sr.begin()?0:(--it)->fi);
	while(1){
		pii t=T2.ask(1,1,m,i,r);
		if(t.fi<=tmp)return;
		int u=-t.se;
		push(u);
		T2.upd(1,1,m,u,mkp(-1e9,-u));
		r=u;
	}
}
vi vec[maxn];

void dele(int u){
	tr.U(u,-1);
	if(!sl.size())return;
	auto it=sr.lower_bound(mkp(u,0)),it2=sl.lower_bound(mkp(u,inf));
	if(it!=sr.end() && it2!=sl.begin())
		--it2,T.add(1,1,m,it->se,it2->se,-1);
}

signed main()
{
	n=read(),m=read();
	For(i,1,n)a[i]=read(),vec[a[i]].pb(i),mx=max(mx,a[i]),tr.U(i,1);
	For(i,1,m)q[i].l=read(),q[i].r=read(),q[i].id=i;
	sort(q+1,q+m+1);
	T.build(1,1,m,1),T2.build(1,1,m,0);
	int R=0;
	For(i,1,m){
		if(q[i].r>R)push(i),R=q[i].r;
		else T2.upd(1,1,m,i,mkp(q[i].r,-i));
	}
	Rep(i,mx+1,0){
		for(int u:vec[i]) dele(u);
		while(T.t[1].fi>=i){
			int u=T.t[1].se;
			del(u),res[q[u].id]=i;
		}
	}
	For(i,1,m)printf("%d\n",res[i]);
	return 0;
}