[UESTCPC 2024] 取数游戏

有一个长度为 $n$ 的序列，第 $i$ 个数的权值为 $a_i$。两位选手 A 和 B 在做游戏，他们将对轮流对序列进行操作。每位选手每次有两种操作可以选择： - 删除序列中的任意两个的数 $a_i,a_j$ $(i \neq j)$，并在序列中添加一个权值为 $a_i+a_j$ 的数。当序列中只有一个数时，不能执行该操作。 - 取走序列中一个数，将序列中剩下的数的权值全部累加给对方，结束游戏。 如果最后 A 得到的权值更多，则他胜利，否则 B 胜利。 A 先进行操作，问他是否有必胜策略。**保证 $a_i$ 之和为奇数。** ## Input 本题包含多组数据。 第一行输入一个整数 $T$ $(1\leq T\leq 10^5)$，表示数据组数。 对于每组数据，输入格式如下。 第一行一个整数 $n$ $(1\leq n\leq 5 \times 10^5)$，表示序列的初始长度。 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$ $(1\leq a_i\leq 10^9)$，表示初始的序列。 数据保证 $\sum n\leq 10^6$ 且 $\sum a_i$ 为奇数。 ## Output 对于每组数据，如果 A 有必胜策略，输出 `YES`，否则输出 `NO`。 [samples] ## Note 样例一解释如下： - 如果 A 选择权值 $3$，则 B 能得到的权值为 $6+4=10$。 - 如果 A 选择权值 $4$，则 B 能得到的权值为 $3+6=9$。 - 如果 A 选择权值 $6$，则 B 能得到的权值为 $3+4=7$。 - 如果 A 选择合并权值 $3,6$，序列变为 $9,4$。若 B 选择权值 $9$，则 A 能得到的权值为 $4$。 - 如果 A 选择合并权值 $3,4$，序列变为 $7,6$。若 B 选择权值 $7$，则 A 能得到的权值为 $6$。 - 如果 A 选择合并权值 $4,6$，序列变为 $10,3$。若 B 选择权值 $10$，则 A 能得到的权值为 $3$。 在所有情况下 B 均能以最优策略取得更高的权值，故 A 无法胜利。 样例二解释如下： 如果 A 选择权值 $2$，则 B 能得到的权值为 $1$。 因此 A 有必胜策略。