#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define int int64_t

#define rng(i, a, b) for (int i = a; i < b; i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = b - 1; i >= a; i--)
#define per(i, b) gnr(i, 0, b)

#define all(x) begin(x), end(x)
#define sz(x) int(size(x))

#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound

#define f first
#define s second

using namespace std;
using namespace __gnu_pbds;

struct Segment {
    int len;
    int pref, suff, mx;

    Segment operator+(Segment b) {
        Segment ret;
        ret.len = len + b.len;
        ret.pref = pref + (pref == len ? b.pref : 0);
        ret.suff = (b.suff == b.len ? suff : 0) + b.suff;
        ret.mx = max({mx, b.mx, suff + b.pref});
        return ret;
    }
};

int tree_sz;
vector<Segment> segtree;

void update(int i, bool v, int x = 0, int tl = 0, int tr = tree_sz) {
    if (tl + 1 == tr) {
        segtree[x] = {1, v, v, v};
        return;
    }
    int mid = (tl + tr) / 2;
    if (i < mid) {
        update(i, v, 2 * x + 1, tl, mid);
    } else {
        update(i, v, 2 * x + 2, mid, tr);
    }
    segtree[x] = segtree[2 * x + 1] + segtree[2 * x + 2];
}

void solve() {
    int n, b;
    cin >> n >> b;

    vector<int> f(n);
    rep(i, n) {
        cin >> f[i];
    }

    vector<array<int, 3>> queries(b);
    rep(i, b) {
        cin >> queries[i][0] >> queries[i][1];
        queries[i][2] = i;
    }
    sort(all(queries));

    vector<int> to_rem(n);
    iota(all(to_rem), 0);
    sort(all(to_rem), [&](int a, int b) {
        return f[a] > f[b];
    });

    tree_sz = 1;
    while (tree_sz < n) {
        tree_sz *= 2;
    }
    segtree.resize(2 * tree_sz, {});
    rep(i, n) {
        update(i, 1);
    }

    vector<bool> ans(b);
    for (auto [mx_d, step, idx] : queries) {
        while (!to_rem.empty() && f[to_rem.back()] <= mx_d) {
            update(to_rem.back(), 0);
            to_rem.pop_back();
        }
        ans[idx] = segtree[0].mx < step;
    }
    rep(i, b) {
        cout << ans[i] << '\n';
    }
}

int32_t main() {
#ifndef LOCAL
    freopen("snowboots.in", "r", stdin);
    freopen("snowboots.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tc = 1;
    // cin >> tc;
    while (tc--) {
        solve();
    }

    return 0;
}