← 返回题目列表

Codeforces · 302/A

A. 尤金尼和阵列

中文机器翻译题面 查看原题

Eugeny 有数组 a = a1, a2, ..., an,由 n 个整数组成。每个整数 ai 等于 -1 或 1。此外,他有 m 个查询:

- 查询号 i 给出为一对整数 li, ri (1 ≤ li ≤ ri ≤ n)。
- 如果数组 a 的元素可以重新排列,使得总和 ali + ali + 1 + ... + ari = 0,则对查询的响应将为整数 1,否则对查询的响应将为整数 0。

帮助尤金尼,回答他所有的疑问。

输入

第一行包含整数 n 和 m (1 ≤ n, m ≤ 2·105)。第二行包含n个整数a1, a2, ..., an (ai = -1, 1)。接下来的 m 行包含尤金的查询。第 i 行包含整数 li, ri (1 ≤ li ≤ ri ≤ n)。

输出

打印 m 个整数 — 按照输入中出现的顺序对 Eugene 查询的响应。

示例

输入 #1

2 3
1 -1
1 1
1 2
2 2

输出 #1

0
1
0

输入 #2

5 5
-1 1 1 1 -1
1 1
2 3
3 5
2 5
1 5

输出 #2

0
1
0
1
0