题目描述

有一个长度为 $n$ 的序列，第 $i$ 个数的权值为 $a_i$。两位选手 A 和 B 在做游戏，他们将对轮流对序列进行操作。每位选手每次有两种操作可以选择：

• 删除序列中的任意两个的数 $a_i,a_j$ $(i \neq j)$，并在序列中添加一个权值为 $a_i+a_j$ 的数。当序列中只有一个数时，不能执行该操作。
• 取走序列中一个数，将序列中剩下的数的权值全部累加给对方，结束游戏。

如果最后 A 得到的权值更多，则他胜利，否则 B 胜利。

A 先进行操作，问他是否有必胜策略。保证 $a_i$ 之和为奇数。

输入格式

本题包含多组数据。

第一行输入一个整数 $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$ 为奇数。

输出格式

对于每组数据，如果 A 有必胜策略，输出 YES，否则输出 NO。

3
3 
3 6 4
2 
1 2
3
2 5 6

NO
YES
NO

提示

样例一解释如下：

• 如果 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 有必胜策略。