← 返回题目列表

Codeforces · 1833/C

C. 弗拉德建造美丽的阵列

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

Vlad 被赋予了一个包含 $$$n$$$ 正整数的数组 $$$a$$$。现在他想从中构建一个漂亮的数组$$$b$$$,长度为$$$n$$$。

如果一个数组中的所有数字都是正数并且具有相同的奇偶校验,则 Vlad 认为该数组是美丽的。也就是说,美丽数组中的所有数字都大于零,并且要么都是偶数,要么都是奇数。

为了构建数组 $$$b$$$,Vlad 可以为每个 $$$b_i$$$ 分配值 $$$a_i$$$ 或 $$$a_i - a_j$$$,其中可以选择从 $$$1$$$ 到 $$$n$$$ 的任何 $$$j$$$。

为了避免尝试做不可能的事情,Vlad 要求你确定是否可以使用他的数组 $$$a$$$ 构建一个长度为 $$$n$$$ 的漂亮数组 $$$b$$$。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

然后按照测试用例的描述进行操作。

每个 case 的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。

每个 case 的第二行包含 $$$n$$$ 正整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

保证所有情况下 $$$n$$$ 的总和不超过 $$$2 \cdot 10^5$$$。

输出

输出$$$t$$$字符串,每个字符串都是对应测试用例的答案。作为答案,如果 Vlad 可以构建一个漂亮的数组 $$$b$$$,则输出“YES”,否则输出“NO”。

您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。

示例

输入 #1

7
5
2 6 8 4 3
5
1 4 7 6 9
4
2 6 4 10
7
5 29 13 9 10000001 11 3
5
2 1 2 4 2
5
2 4 5 4 3
4
2 5 5 4

输出 #1

NO
YES
YES
YES
YES
NO
NO