题目描述

给定一个长度为 $N$ 的非负整数序列 $A=(A_1,A_2,\dots,A_N)$。其中 $S=\sum_{i=1}^{N} A_i$ 是偶数。

请判断是否存在满足以下条件的长度为 $N$ 的非负整数序列对 $B=(B_1,B_2,\dots,B_N)$ 和 $C=(C_1,C_2,\dots,C_N)$。

• 对于所有 $i=1,2,\dots,N$，都有 $B_i+C_i=A_i$。
• 对于任意长度为 $N$ 的整数序列 $X=(X_1,X_2,\dots,X_N)$，如果对于每个 $i$，$X_i=B_i$ 或 $X_i=C_i$，则 $\sum_{i=1}^{N} X_i \neq \frac{S}{2}$。

请针对 $T$ 组测试用例分别作答。

输入格式

输入通过标准输入给出，格式如下：

$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$

每组测试用例如下格式：

$N$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出 $T$ 行。对于第 $i$ 个测试用例，如果存在满足条件的 $B,C$，则输出 Yes，否则输出 No。

样例 1

输入

3
3
1 2 3
6
1 1 2 2 3 3
4
1 1 1000000000 1000000000

输出

Yes
No
Yes

说明/提示

限制条件

• $1 \leq T$
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• $\sum_{i=1}^{N} A_i$ 是偶数
• 所有测试用例中 $N$ 的总和不超过 $2 \times 10^5$
• 输入的所有数均为整数

样例解释 1

对于第 $1$ 个测试用例，取 $B=(1,1,3),\ C=(0,1,0)$ 可以满足条件。对于第 $2$ 个测试用例，不存在满足条件的 $B,C$。

由 ChatGPT 4.1 翻译