AC!

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 7;
struct shoe
{
	int step;
	int dep;
	int id;
} boo[MAX];
struct brick
{
	int snow;
	int id;
} bri[MAX];
bool cmp1(shoe a, shoe b)
{
	return a.dep > b.dep;
}
bool cmp2(brick a, brick b)
{
	return a.snow > b.snow;
}
int cnt = 1;
int color[MAX], cross[MAX];
int fa[MAX];
int maxcross = 0;
int Cout[MAX];
inline int find(int x)
{
	if (x == fa[x])
		return x;
	return fa[x] = find(fa[x]);
}
int read()
{
	int num = 0, bj = 0;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
		{
			bj = 1;
		}
		ch = getchar();
	}
	while (isdigit(ch))
	{
		num = num * 10 + ch - '0';
		ch = getchar();
	}
	return bj ? -num : num;
}
int main()
{
	int N, M;
	cin >> N >> M;
	for (register int i = 1; i <= N; i++)
	{
		bri[i].snow = read();
		bri[i].id = i;
	}
	for (register int i = 1; i <= M; i++)
	{
		boo[i].dep = read();
		boo[i].step = read();
		boo[i].id = i;
	}
	sort(bri + 1, bri + 1 + N, cmp2);
	sort(boo + 1, boo + 1 + M, cmp1);
	for (register int i = 1; i <= N; i++)
	{
		cross[i] = 1;
		fa[i] = i;
	}
	for (register int i = 1; i <= M; i++)
	{
		while (cnt <= N && bri[cnt].snow > boo[i].dep)
		{
			maxcross = max(maxcross, 1);
			color[bri[cnt].id] = 1;
			if (color[bri[cnt].id - 1])
			{
				int x = find(bri[cnt].id - 1), y = find(bri[cnt].id);
				fa[x] = y;
				cross[y] += cross[x];			 
				maxcross = max(maxcross, cross[y]);
			}
			if (color[bri[cnt].id + 1])
			{
				int x = find(bri[cnt].id), y = find(bri[cnt].id + 1);
				fa[x] = y;
				cross[y] += cross[x];
				maxcross = max(maxcross, cross[y]); 
			}
			cnt++;
		}
		if (maxcross < boo[i].step)
		{
			Cout[boo[i].id] = 1;
		}
	}
	for (register int i = 1; i <= M; i++)
	{
		printf("%d\n", Cout[i]);
	}
}