# include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
int n,m,ans[500010];
pii a[500010];
struct Query
{
	int l,r,id;
	bool operator<(const Query &t)const{return l!=t.l?l<t.l:r>t.r;}
}qry[500010];
struct Node
{
	int x,id;
	Node(int x,int i):x(x),id(i){}
	bool operator<(const Node &t)const{return x<t.x;}
};
set<Node> sL,sR;
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]={0,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,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 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);
	sL.emplace(0,0);sR.emplace(n+1,m+1);
	for(int i=S1::maxn[1];i;i=S1::query(1,1,m,1,i-1))
	{
		sL.emplace(qry[i].l,i);sR.emplace(qry[i].r,i);
		S2::update(1,1,m,i,qry[i].r-qry[i].l+1);
	}
	for(int i=1,j;i<=n;i=j)
	{
		while(S2::maxn[1].first>=a[i].first+1)
		{
			int k=S2::maxn[1].second;
			ans[qry[k].id]=S2::maxn[1].first;
			assert(BIT::query(qry[k].l,qry[k].r)==ans[qry[k].id]);
			S1::update(1,1,m,k);
			S2::update(1,1,m,k,0);
			int le=prev(sL.erase(sL.find(Node(qry[k].l,k))))->id,ri=sR.erase(sR.find(Node(qry[k].r,k)))->id;
			for(int p=S1::query(1,1,m,1,ri-1);p!=le;p=S1::query(1,1,m,1,p-1))
			{
				assert(sL.emplace(qry[p].l,p).second);
				assert(sR.emplace(qry[p].r,p).second);
				S2::update(1,1,m,p,BIT::query(qry[p].l,qry[p].r));
			}
		}
		for(j=i;j<=n && a[i].first==a[j].first;j++);
		for(;i<j;i++)
		{
			int l=sR.lower_bound(Node(a[i].second,0))->id,r=(--sL.upper_bound(Node(a[i].second,0)))->id;
			if(l<=r) S2::update(1,1,m,l,r,-1);
			BIT::update(a[i].second,-1);
		}
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}