//程序算法：线段树，排序 
#include <bits/stdc++.h>
using namespace std;
const int N=100010,M=1000010,INF=0x3f3f3f3f;
/*
    用线段树维护序列 a,初始全为 1。
	将 s[i] 从小到大排序，
	对于每个 s[i]，将原序列不大于s[i]的数对应的a[i]都设为-INF。
	线段树求最大字段和。 
*/ 
int n,m,f[N],Hash[M];
struct Node{
	int l,r;
	int max,sum,lmax,rmax;
}t[N*4];
struct Query{
	int s,d;
	int ans,id;
}q[M];
void pushup(int rt)
{
	int l=rt*2,r=rt*2+1;
	t[rt].sum=t[l].sum+t[r].sum;
	t[rt].lmax=max(t[l].lmax,t[l].sum+t[r].lmax);
	t[rt].rmax=max(t[r].rmax,t[r].sum+t[l].rmax);
	t[rt].max=max(max(t[l].max,t[r].max),t[l].rmax+t[r].lmax);
}
void build(int rt,int l,int r)
{
	t[rt].l=l,t[rt].r=r;
	if(l==r)
	{
		t[rt].sum=t[rt].max=t[rt].lmax=t[rt].rmax=1;
		return;
	}
	int mid=(l+r)>>1;
	build(rt*2,l,mid);
	build(rt*2+1,mid+1,r);
	pushup(rt);
}
void modify(int rt,int x,int v)
{
	if(t[rt].l==t[rt].r)
	{
		t[rt].sum=t[rt].max=t[rt].lmax=t[rt].rmax=v;
		return;
	}
	int mid=(t[rt].l+t[rt].r)>>1;
	if(x<=mid)modify(rt*2,x,v);
	else modify(rt*2+1,x,v);
	pushup(rt);
}
vector<int> vec[M];
bool cmp(Query x,Query y)
{
	return x.s<y.s;
}
bool cmp2(Query x,Query y)
{
	return x.id<y.id;
}
int main()
{
	scanf("%d %d",&n,&m);
	int len=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&f[i]);
		Hash[++len]=f[i];
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&q[i].s,&q[i].d);
		q[i].id=i;
		Hash[++len]=q[i].s;
	}
	sort(Hash+1,Hash+len+1);
	len=unique(Hash+1,Hash+len+1)-Hash-1;
	sort(q+1,q+m+1,cmp);
	for(int i=1;i<=n;i++)
	{
		int h=lower_bound(Hash+1,Hash+len+1,f[i])-Hash;
		//离散化。 
		vec[h].push_back(i);
	}
	build(1,1,n);
	int p=0;
	for(int i=1;i<=m;i++)
	{
		int tmp=lower_bound(Hash+1,Hash+len+1,q[i].s)-Hash;
		while(p<tmp)
		{
			p++;
			for(auto& x:vec[p])
				modify(1,x,-INF);
			
		}
		q[i].ans=(t[1].max<q[i].d);
	}
	sort(q+1,q+m+1,cmp2);//排序成原序。
	for(int i=1;i<=m;i++)
		printf("%d\n",q[i].ans); 
	return 0;
}