#include <bits/stdc++.h>

using namespace std;

// typedef long long int;

const int MAXN = 100000, MAXB = 100000;

map<int, int> m;
int v[MAXN];
int vals[MAXN + MAXB];
pair<int, int> boots[MAXB];
vector<int> tiles[MAXN + MAXB];
set<int> r;
int mi[MAXN + MAXB];


int main() {
    freopen("snowboots.in", "r", stdin);
    freopen("snowboots.out", "w", stdout);


    int n, b;
    cin >> n >> b;


    for (int i = 0; i < n; i++) {
        cin >> v[i];
        vals[i]=v[i];
    }



    for (int i = 0; i < b; i++) {
        cin >> boots[i].first >> boots[i].second;
        vals[n + i] = (boots[i].first);
    }

    sort(vals, vals + (n+b) );
    int cur = 0;
    m[vals[0]]=cur;
    for (int i = 1; i < n + b; i++) {
        if (vals[i]!=vals[i-1])cur++;
        m[vals[i]]=cur;
    }



    for (int i = 0; i < n; i++) {
        v[i]=m[v[i]];
    }
    for (int i = 0; i < n; i++) {
        // cout << boots[i].second << m[boots[i].second] << endl;
        boots[i].first=m[boots[i].first];
    }

    for (int i = 1; i < n-1; i++) {
        tiles[v[i]].push_back(i);
    }


    for (int i = 0; i < n; i++) r.insert(i);
    int ans = 1;

    // for (auto val: v) cout << val << ' ';
    // cout << endl;
    for (int d = n + b - 1; d >= 0; d--) {
        // cout << d << ans << endl;
        mi[d]=ans;
        for (auto val: tiles[d]) {
            auto it = r.find(val);
            if (it == r.begin() || it == r.end() || next(it, 1) == r.end()) {

                continue;
            }
            auto nextt = next(it, 1);
            auto prevv = prev(it, 1);

            r.erase(it);
            ans=max(ans, *nextt - *prevv);
        }


    }
    for (int i = 0; i < b; i++) {
        // cout << boots[i].first << boots[i].second << endl;
        if (boots[i].second >= mi[boots[i].first]) {
            cout << 1 << endl;
        } else cout << 0 << endl;
    }
    return 0;
}