#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define ls (p << 1)
#define rs (p << 1 | 1)
bool ans[N];
int n, m;
int a[N], b[N], cnt;
struct shoes {
	int s, d, id;
	bool operator<(const shoes ert) const {
		return s < ert.s;
	}
} pr[N];
int val[N];
vector <int> t[N];
struct node {
	int l, r, pre, suf, ans;
} tr[N << 2];
node pushup(node x, node y) {
	node tmp = {x.l, y.r, 0, 0, 0};
	if (x.r - x.l + 1 == x.pre) tmp.pre = x.pre + y.pre;
	else tmp.pre = x.pre;
	if (y.r - y.l + 1 == y.suf) tmp.suf = x.suf + y.suf;
	else tmp.suf = y.suf;
	tmp.ans = max(max(x.ans, y.ans), x.suf + y.pre);
	return tmp;
}
void build(int p, int l, int r) {
	if (l == r) return tr[p] = {l, r, 1, 1, 1}, void();
	int mid = (l + r) >> 1;
	build(ls, l, mid); build(rs, mid + 1, r);
	tr[p] = pushup(tr[ls], tr[rs]);
}
void update(int p, int l, int r, int id) {
	if (l == r) return tr[p] = {l, r, 0, 0, 0}, void();
	int mid = (l + r) >> 1;
	if (id <= mid) update(ls, l, mid, id);
	else update(rs, mid + 1, r, id);
	tr[p] = pushup(tr[ls], tr[rs]);
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i], b[++cnt] = a[i];
	for (int i = 1; i <= m; i++)
		cin >> pr[i].s >> pr[i].d, pr[i].id = i, b[++cnt] = pr[i].s;
	sort(b + 1, b + cnt + 1), sort(pr + 1, pr + m + 1);
	for (int i = 1; i <= m; i++) {
		pr[i].s = lower_bound(b + 1, b + cnt + 1, pr[i].s) - b;
		val[i] = pr[i].s;
	}
	for (int i = 1, id; i <= n; i++) {
		a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
		id = lower_bound(val + 1, val + m + 1, a[i]) - val;
		t[id].push_back(i);
	}
	build(1, 1, n);
	for (int i = 1; i <= m; i++) {
		for (auto j : t[i]) update(1, 1, n, j);
		if (tr[1].ans < pr[i].d) ans[pr[i].id] = true;
	}
	for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
}