#include<bits/stdc++.h>
using namespace std;
#define N 500050
typedef long long ll;
const int inf=0x3f3f3f3f;
typedef pair<int,int> pii;
const pii Min=make_pair(-inf,0);
int n,m,a[N],ans[N];
struct Query{
	int id,l,r;
}q[N];
class BIT{
	int b[N];
	inline int lowbit(int x){return x&(-x);}
public:
	void Add(int x,int d){
		while(x<=n)b[x]+=d,x+=lowbit(x);
	}
	int Ask(int x){
		int ans=0;
		while(x)ans+=b[x],x-=lowbit(x);
		return ans;
	}
	int Query(int l,int r){
		if(l>r)return 0;
		return Ask(r)-Ask(l-1);
	}
}B;
class Segment_Tree_2{
	int Len;
	struct node{
		pii mx;
		int add;
		node(){mx=Min;}
		inline void Add(int d){
			mx.first+=d;
			add+=d;
		}
	}t[N<<2];
	#define ls u<<1
	#define rs u<<1|1
	inline void update(int u){
		t[u].mx=max(t[ls].mx,t[rs].mx);
	}
	inline void pushdown(int u){
		if(t[u].add){
			t[ls].Add(t[u].add);
			t[rs].Add(t[u].add);
			t[u].add=0;
		}
	}
	void _ins(int u,int L,int R,int x,pii d){
		if(L==R){
			t[u].mx=d;
			return;
		}
		pushdown(u);
		int mid=(L+R)>>1;
		x<=mid?_ins(ls,L,mid,x,d):_ins(rs,mid+1,R,x,d);
		update(u);
	}
	void _add(int u,int L,int R,int l,int r,int d){
		if(L>=l&&R<=r){
			t[u].Add(d);
			return;
		}
		pushdown(u);
		int mid=(L+R)>>1;
		if(l<=mid)_add(ls,L,mid,l,r,d);
		if(r>mid)_add(rs,mid+1,R,l,r,d);
		update(u);
	}
public:
	void init(int _n){
		Len=_n;
	}
	void Ins(int p,pii d){
		_ins(1,1,Len,p,d);
	}
	pii get_max(){
		return t[1].mx;
	}
	void Plus(int l,int r,int d){
		if(l>r)return;
		_add(1,1,Len,l,r,d);
	}
}T;
class Segment_Tree_1{
	int Len;
	struct node{
		pii mx;
		node(){mx=Min;}
	}t[N<<2];
	inline void update(int u){
		t[u].mx=max(t[ls].mx,t[rs].mx);
	}
	void _ins(int u,int L,int R,int x,pii d){
		if(L==R){
			t[u].mx=d;
			return;
		}
		int mid=(L+R)>>1;
		x<=mid?_ins(ls,L,mid,x,d):_ins(rs,mid+1,R,x,d);
		update(u);
	}
	pii _ask(int u,int L,int R,int l,int r){
		if(L>=l&&R<=r){
			return t[u].mx;
		}
		int mid=(L+R)>>1;
		pii ans=Min;
		if(l<=mid)ans=max(ans,_ask(ls,L,mid,l,r));
		if(r>mid)ans=max(ans,_ask(rs,mid+1,R,l,r));
		return ans;
	}
public:
	void init(int _n){
		Len=_n;
	}
	void Ins(int p,pii d){
		_ins(1,1,Len,p,d);
	}
	pii Ask(int l,int r){
		return _ask(1,1,Len,l,r);
	}
}H;
set<pii> Sl,Sr;
void Insert(int u){
	Sl.emplace(q[u].l,u);
	Sr.emplace(q[u].r,u);
	T.Ins(u,pii(B.Query(q[u].l,q[u].r),u));
}
void Delete(int u){
	auto it=Sl.erase(Sl.find(pii(q[u].l,u)));
	int R=it==Sl.end()?m:it->second;
	it=Sr.erase(Sr.find(pii(q[u].r,u)));
	int lim=it==Sr.begin()?0:(--it)->first;
	while(true){
		auto [r,v]=H.Ask(u,R);
		v=-v;
		if(r<=lim)break;
		H.Ins(v,Min);
		Insert(v);
	}
	T.Ins(u,Min);
}
vector<int> p[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		p[a[i]].push_back(i);
		B.Add(i,1);
	}
	for(int i=1;i<=m;++i){
		cin>>q[i].l>>q[i].r;
		q[i].id=i;
	}
	sort(q+1,q+m+1,[&](Query a,Query b){
		return a.l==b.l?(a.r==b.r?a.id<b.id:a.r>b.r):a.l<b.l;
	});
	H.init(m);
	T.init(m);
	for(int i=1,ri=-1;i<=m;++i){
		if(q[i].r>ri){
			Insert(i);
			ri=q[i].r;
		}
		else{
			H.Ins(i,pii(q[i].r,-i));
		}
	}
	for(int i=500001;i>=0;--i){
		for(auto x:p[i]){
			B.Add(x,-1);
			if(!Sl.empty()){
				auto itl=Sr.lower_bound(pii(x,0));
				auto itr=Sl.lower_bound(pii(x,inf));
				if(itl!=Sr.end()&&itr!=Sl.begin()){
					int l=itl->second,r=(--itr)->second;
					T.Plus(l,r,-1);
				}
			}
		}
		while(true){
			auto [sum,u]=T.get_max();
			if(sum>=i){
				ans[q[u].id]=i;
				Delete(u);
			}
			else{
				break;
			}
		}
	}
	for(int i=1;i<=m;++i){
		cout<<ans[i]<<'\n';
	}
	return 0;
}