到冬天了，这意味着下雪了！从农舍到牛棚的路上有N块地砖，方便起见编号为1…N，第i块地砖上积了fi英尺的雪。在Farmer John的农舍的地窖中，总共有B双靴子，编号为1…B。其中某些比另一些结实，某些比另一些轻便。具体地说，第i双靴子能够让FJ在至多si英尺深的积雪中行走，能够让FJ每步至多前进di。Farmer John从1号地砖出发，他必须到达N号地砖才能叫醒奶牛们。1号地砖在农舍的屋檐下，N号地砖在牛棚的屋檐下，所以这两块地砖都没有积雪。帮助Farmer John求出哪些靴子可以帮助他走完这段艰辛的路程。

第二行包含N个空格分隔的整数；第i个整数为fi，即i号地砖的积雪深度（0≤fi≤10^9）。输入保证f1=fN=0

下面B行，每行包含两个空格分隔的整数。第i+2行的第一个数为si，表示第i双靴子能够承受的最大积雪深度。

第i+2行的第二个数为di，表示第i双靴子的最大步长。输入保证0≤si≤10^9以及1≤di≤N-1

第i行包含一个整数：如果Farmer John能够穿着第i双靴子从1号地砖走到N号地砖，为1，否则为0

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#include<vector>

#include<map>

#include<set>

#define pa pair<LL,LL>

#define LL long long

using namespace std;

inline int read(){

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

inline void Out(int a){

    if(a>9) Out(a/10);

    putchar(a%10+'0');

}

const LL inf=1e9+10;

const LL mod=1e9+7;

const int N=1e5+50;

int n,m,cnt=1;

struct date{

    int v,id;

}f[N];

bool cmpd(date A,date B){

    return A.v<B.v;

}

struct xie{

    int s,d,id;

}a[N];

bool cmpx(xie A,xie B){

    return A.s<B.s;

}

set<int> S;

priority_queue<int> P,Q;

void del(int x){

    Q.push(x);

    while(Q.empty()==0&&P.empty()==0&&Q.top()==P.top()){

        P.pop();Q.pop();

    }

}

void add(int x){

    P.push(x);

}

int ans[N];

int main(){

    n=read();m=read();

    if(n==1||n==2){

        for(int i=1;i<=m;++i){

            putchar('1');puts("");

        }

        return 0;

    }

    f[1].v=read();

    for(int i=2;i<n;++i){

        f[i].v=read();f[i].id=i;

    }

    f[n].v=read();

    f[1]=f[n-1];

    n=n-2;

    for(int i=1;i<=m;++i){

        a[i].s=read();a[i].d=read();a[i].id=i;

    }

    sort(f+1,f+1+n,cmpd);

    sort(a+1,a+1+m,cmpx);

    P.push(n+1);

    set<int>::iterator L,R;

    int l,r;

    S.insert(1);S.insert(n+2);

    for(int i=1,j=1;j<=m;++j){

        while(i<=n&&f[i].v<=a[j].s){

            R=S.lower_bound(f[i].id);

            L=R;--L;

            l=*L;r=*R;

            del(r-l);

            add(f[i].id-l);

            add(r-f[i].id);

            S.insert(f[i].id);

            ++i;

        }

        if(P.top()<=a[j].d) ans[a[j].id]=1;

        else ans[a[j].id]=0;

    }

    for(int i=1;i<=m;++i) printf("%d\n",ans[i]);

    return 0;

}