//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
#define ls (x<<1)
#define rs (ls|1)
int n,q;
int a[500500];
int l[500500],r[500500];
namespace seg1
{
	/*
	维护所有当前候选段，满足两两不包含，对左端点建线段树，对应左端点不存在区间时右端点值设为 -1。
	val 维护区间权值的最大值，当有一个区间权值非负的时候删除它，然后调用 seg2 补足新的区间。
	支持区间加，区间查 max，查 max 位置，线段树上二分右端点。
	*/
	int rmx[500500<<2];
	int val[500500<<2],tag[500500<<2];
	void build(int x,int l,int r)
	{
		val[x]=-inf;
		if(l==r) return ;
		int mid=(l+r)/2;
		build(ls,l,mid);
		build(rs,mid+1,r);
	}
	void pushdown(int x,int l,int r)
	{
		val[x]+=tag[x];
		if(l!=r)
		{
			tag[ls]+=tag[x];
			tag[rs]+=tag[x];
		}
		tag[x]=0;
	}
	void pushup(int x,int l,int r)
	{
		int mid=(l+r)/2;
		pushdown(ls,l,mid);
		pushdown(rs,mid+1,r);
		rmx[x]=max(rmx[ls],rmx[rs]);
		val[x]=max(val[ls],val[rs]);
	}
	void modify(int x,int l,int r,int p,int pr,int v)
	{
		pushdown(x,l,r);
		if(l==r)
		{
			rmx[x]=pr;
			val[x]=v;
			return ;
		}
		int mid=(l+r)/2;
		if(p<=mid)
			modify(ls,l,mid,p,pr,v);
		else
			modify(rs,mid+1,r,p,pr,v);
		pushup(x,l,r);
	}
	void update(int x,int l,int r,int ql,int qr,int v)
	{
		if(ql>qr) return ;
		pushdown(x,l,r);
		if(ql<=l&&r<=qr)
		{
			tag[x]+=v;
			return ;
		}
		int mid=(l+r)/2;
		if(ql<=mid)
			update(ls,l,mid,ql,qr,v);
		if(qr>mid)
			update(rs,mid+1,r,ql,qr,v);
		pushup(x,l,r);
	}
	int find(int x,int l,int r,int val)
	{
		if(rmx[x]<val) return r+1;
		if(l==r) return l;
		int mid=(l+r)/2;
		if(rmx[ls]<val) return find(rs,mid+1,r,val);
		return find(ls,l,mid,val);
	}
	pii getPositive(int x,int l,int r)
	{
		pushdown(x,l,r);
		if(l==r)
			return mp(l,rmx[x]);
		int mid=(l+r)/2;
		pushdown(ls,l,mid);
		if(val[ls]>=0)
			return getPositive(ls,l,mid);
		return getPositive(rs,mid+1,r);
	}
	int getMax()
	{
		pushdown(1,1,n);
		return val[1];
	}
}
namespace seg2
{
	/*
	对每个左端点维护所有替补区间，每次查找区间的时候需要找左端点最小的满足右端点大于某个值的区间中最长的一个。
	需要支持线段树上二分来找这个区间。
	*/
	int rmx[500500<<2];
	void modify(int x,int l,int r,int p,int v)
	{
		if(l==r)
		{
			rmx[x]=v;
			return ;
		}
		int mid=(l+r)/2;
		if(p<=mid)
			modify(ls,l,mid,p,v);
		else
			modify(rs,mid+1,r,p,v);
		rmx[x]=max(rmx[ls],rmx[rs]);
	}
	pii findNext(int x,int l,int r,int ql,int qr,int bound)
	{
		if(ql<=l&&r<=qr)
		{
			if(rmx[x]<bound)
				return mp(-1,-1);
			if(l==r)
				return mp(l,rmx[x]);
			int mid=(l+r)/2;
			if(rmx[ls]<bound)
				return findNext(rs,mid+1,r,ql,qr,bound);
			return findNext(ls,l,mid,ql,qr,bound);
		}
		int mid=(l+r)/2;
		if(ql>mid)
			return findNext(rs,mid+1,r,ql,qr,bound);
		if(qr<=mid)
			return findNext(ls,l,mid,ql,qr,bound);
		pii pr=findNext(ls,l,mid,ql,qr,bound);
		if(pr.first!=-1) return pr;
		return findNext(rs,mid+1,r,ql,qr,bound);
	}
	int query(int x,int l,int r,int ql,int qr)
	{
		if(ql>qr) return 0;
		if(ql==l&&qr==r) return rmx[x];
		int mid=(l+r)/2;
		if(qr<=mid)
			return query(ls,l,mid,ql,qr);
		if(ql>mid)
			return query(rs,mid+1,r,ql,qr);
		return max(query(ls,l,mid,ql,mid),query(rs,mid+1,r,mid+1,qr));
	}
	int findNext(int x,int l,int r,int p)
	{
		if(r<=p) return r+1;
		if(!rmx[x]) return r+1;
		if(l==r) return l;
		if(l>=p)
		{
			int mid=(l+r)/2;
			if(rmx[ls]) return findNext(ls,l,mid,p);
			return findNext(rs,mid+1,r,p);
		}
		int mid=(l+r)/2;
		if(mid<=p)
			return findNext(rs,mid+1,r,p);
		int ret=findNext(ls,l,mid,p);
		if(ret==mid+1) return findNext(rs,mid+1,r,p);
		return ret;
	}
}
namespace bit
{
	int val[500500];
	void update(int p,int v)
	{
		while(p<500500)
		{
			val[p]+=v;
			p+=(p&(-p));
		}
	}
	int query(int p)
	{
		int ans=0;
		while(p)
		{
			ans+=val[p];
			p-=(p&(-p));
		}
		return ans;
	}
}
vector<int> vec[500500];
int cur;
vector<int> pool[500500];
void refresh(int l,int r,int lim)
{
	int lst=lim;
	while(l<=r)
	{
		pii pr=seg2::findNext(1,1,n,l,n,lst);
		if(pr.first==-1) return ;
		if(pr.first>r) return ;
		seg2::modify(1,1,n,pr.first,0);
		seg1::modify(1,1,n,pr.first,pr.second,bit::query(pr.second)-bit::query(pr.first-1)-cur);
		if(sz(vec[pr.first]))
		{
			int pr2=vec[pr.first].back();
			seg2::modify(1,1,n,pr.first,pr2);
			vec[pr.first].pop_back();
		}
		l=pr.first+1;
		lst=pr.second+1;
	}
}
map<pii,int> Answer;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=q;i++)
		cin>>l[i]>>r[i];
	for(int i=1;i<=q;i++)
		vec[l[i]].pb(r[i]);
	for(int i=1;i<=n;i++)
		srt(vec[i]);
	seg1::build(1,1,n);
	for(int i=1;i<=n;i++)
		if(sz(vec[i]))
		{
			seg2::modify(1,1,n,i,vec[i].back());
			vec[i].pop_back();
		}
	for(int i=1;i<=n;i++)
		bit::update(i,1);
	for(int i=1;i<=n;i++)
		pool[a[i]].pb(i);
	cur=500005;
	refresh(1,n,0);
	while(cur)
	{
		for(auto x:pool[cur])
		{
			int p=seg1::find(1,1,n,x);
			seg1::update(1,1,n,p,x,-1);
			bit::update(x,-1);
		}
		while(seg1::getMax()>=0)
		{
			pii pr=seg1::getPositive(1,1,n);
			Answer[pr]=cur;
			seg1::modify(1,1,n,pr.first,0,-inf);
			refresh(pr.first,seg2::findNext(1,1,n,pr.first),seg2::query(1,1,n,1,pr.first-1));
		}
		cur--;
		seg1::update(1,1,n,1,n,1);
	}
	for(int i=1;i<=q;i++)
		cout<<Answer[mp(l[i],r[i])]<<'\n';
	return 0;
}