# include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
constexpr int INF=1e9;
int n,m,ans[500010];
pii a[500010];
set<int> st;
struct Query
{
	int l,r,id;
	Query(){}
	Query(int l):l(l){}
	bool operator<(const Query &t)const{return l<t.l;}
}qry[500010];
namespace BIT
{
	int sum[500010];
	void update(int x,int y){for(int i=x;i<=n;i+=i&-i) sum[i]+=y;}
	int query(int x)
	{
		int ans=0;
		for(int i=x;i;i-=i&-i) ans+=sum[i];
		return ans;
	}
	inline int query(int l,int r){return query(r)-query(l-1);}
}
namespace S1
{
	int maxn[1100000];
	int getmax(int x,int y)
	{
		if(!x || !y) return x+y;
		else return (qry[x].r!=qry[y].r?qry[x].r>qry[y].r:qry[x].l<qry[y].l)?x:y;
	}
	void pushup(int rt){maxn[rt]=getmax(maxn[rt*2],maxn[rt*2+1]);}
	void build(int rt,int l,int r)
	{
		if(l==r) return void(maxn[rt]=l);
		int mid=(l+r)/2;
		build(rt*2,l,mid);
		build(rt*2+1,mid+1,r);
		pushup(rt);
	}
	void update(int rt,int l,int r,int x)
	{
		if(l==r) return void(maxn[rt]=0);
		int mid=(l+r)/2;
		if(x<=mid) update(rt*2,l,mid,x);
		else update(rt*2+1,mid+1,r,x);
		pushup(rt);
	}
	int query(int rt,int l,int r,int x,int y)
	{
		if(l>y || r<x) return 0;
		if(l>=x && r<=y) return maxn[rt];
		int mid=(l+r)/2;
		return getmax(query(rt*2,l,mid,x,y),query(rt*2+1,mid+1,r,x,y));
	}
}
namespace S2
{
	int addmk[1100000];
	pii maxn[1100000];
	void pushtag(int rt,int x){maxn[rt].first+=x;addmk[rt]+=x;}
	void pushdown(int rt)
	{
		if(!addmk[rt]) return;
		pushtag(rt*2,addmk[rt]);
		pushtag(rt*2+1,addmk[rt]);
		addmk[rt]=0;
	}
	void pushup(int rt){maxn[rt]=max(maxn[rt*2],maxn[rt*2+1]);}
	void build(int rt,int l,int r)
	{
		if(l==r) return void(maxn[rt]={-INF,l});
		int mid=(l+r)/2;
		build(rt*2,l,mid);
		build(rt*2+1,mid+1,r);
	}
	void update(int rt,int l,int r,int x,int y)
	{
		if(l==r) return void(maxn[rt].first=y);
		pushdown(rt);
		int mid=(l+r)/2;
		if(x<=mid) update(rt*2,l,mid,x,y);
		else update(rt*2+1,mid+1,r,x,y);
		pushup(rt);
	}
	void update(int rt,int l,int r,int x,int y,int z)
	{
		if(l>y || r<x) return;
		if(l>=x && r<=y) return pushtag(rt,z);
		pushdown(rt);
		int mid=(l+r)/2;
		update(rt*2,l,mid,x,y,z);
		update(rt*2+1,mid+1,r,x,y,z);
		pushup(rt);
	}
}
int getle(int x)
{
	int l=1,r=m,mid;
	while(l<r)
	{
		mid=(l+r)/2;
		if(qry[mid].r>=x) r=mid;
		else l=mid+1;
	}
	return l;
}
int getri(int x)
{
	int l=1,r=m,mid;
	while(l<r)
	{
		mid=(l+r+1)/2;
		if(qry[mid].l<=x) l=mid;
		else r=mid-1;
	}
	return l;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i].first);a[i].second=i;
		BIT::update(i,1);
	}
	sort(a+1,a+n+1,greater<pii>());
	for(int i=1;i<=m;i++) scanf("%d%d",&qry[i].l,&qry[i].r),qry[i].id=i;
	sort(qry+1,qry+m+1);
	S1::build(1,1,m);
	S2::build(1,1,m);
	for(int i=S1::maxn[1];i;i=S1::query(1,1,m,1,i-1))
	{
		st.insert(i);
		S2::update(1,1,m,i,qry[i].r-qry[i].l-a[1].first);
	}
	for(int i=1,j;i<=n;i=j)
	{
		while(S2::maxn[1].first>=0)
		{
			int k=S2::maxn[1].second;
			ans[qry[k].id]=a[i].first+1;
			S1::update(1,1,m,k);
			S2::update(1,1,m,k,-INF);
			auto it=st.find(k);
			int ri=(it==--st.end()?m+1:*next(it)),le=(it==st.begin()?0:*prev(it));
			st.erase(it);
			for(int p=S1::query(1,1,m,1,ri-1);p!=le;p=S1::query(1,1,m,1,p-1))
			{
				st.insert(p);
				S2::update(1,1,m,p,BIT::query(qry[p].l,qry[p].r)-a[i].first-1);
			}
		}
		for(j=i;j<=n && a[i].first==a[j].first;j++);
		S2::pushtag(1,a[i].first-a[j].first);
		for(;i<j;i++)
		{
			S2::update(1,1,m,getle(a[i].second),getri(a[i].second),-1);
			BIT::update(a[i].second,-1);
		}
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}