Eugeny and Array

题意翻译

给定一个长度为 $n$ 的序列 $a$，以及 $m$ 个询问。保证 $a_i$ 要么等于 $1$ 要么等于 $-1$。 对于每一个询问，一行两个正整数 $l_i,r_i$，表示查询是否存在一种方案使得将 $a$ 重新排列后可以使得 $a$ 中 $[l_i,r_i]$ 之间所有数之和等于 $0$。若存在，输出 $1$；若不存在，则输出 $0$。

题目描述

Eugeny has array $ a=a_{1},a_{2},...,a_{n} $ , consisting of $ n $ integers. Each integer $ a_{i} $ equals to -1, or to 1. Also, he has $ m $ queries: - Query number $ i $ is given as a pair of integers $ l_{i} $ , $ r_{i} $ $ (1<=l_{i}<=r_{i}<=n) $ . - The response to the query will be integer $ 1 $ , if the elements of array $ a $ can be rearranged so as the sum $ a_{li}+a_{li}+1+...+a_{ri}=0 $ , otherwise the response to the query will be integer $ 0 $ . Help Eugeny, answer all his queries.

输入输出格式

输入格式

The first line contains integers $ n $ and $ m $ $ (1<=n,m<=2·10^{5}) $ . The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ $ (a_{i}= $ - $ 1,1) $ . Next $ m $ lines contain Eugene's queries. The $ i $ -th line contains integers $ l_{i},r_{i} $ $ (1<=l_{i}<=r_{i}<=n) $ .

输出格式

Print $ m $ integers — the responses to Eugene's queries in the order they occur in the input.

输入输出样例

输入样例 #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