题目描述

Mihai 和 Bianca 正在玩糖果袋的游戏。他们有一排 $a$，共有 $n$ 个糖果袋。第 $i$ 个袋子里有 $a_i$ 颗糖果。糖果袋会按照从第一个到第 $n$ 个的顺序分给两位玩家。

如果某个袋子里的糖果数是偶数，Mihai 会拿走这个袋子。否则，Bianca 会拿走这个袋子。每当一个袋子被拿走时，袋子里的糖果数会加入拿到该袋子的玩家的总糖果数中。

Mihai 想要炫耀一下，所以他希望能够重新排列糖果袋，使得在任意时刻（除了一开始两人都没有糖果时），Mihai 的糖果数都严格多于 Bianca。请你帮 Mihai 判断是否存在这样一种重新排列的方法。

输入格式

输入的第一行包含一个整数 $t$（$1 \leq t \leq 1000$）——表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 100$）——表示糖果袋的数量。

每个测试用例的第二行包含 $n$ 个用空格分隔的整数 $a_i$（$1 \leq a_i \leq 100$）——表示每个糖果袋中的糖果数。

输出格式

对于每个测试用例，如果存在满足条件的重新排列方式，输出 "YES"（不带引号）；否则输出 "NO"（不带引号）。

你可以用任意大小写输出答案（例如，"yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定答案）。

样例

3
4
1 2 3 4
4
1 1 1 2
3
1 4 3

YES
NO
NO

样例说明

在第一个测试用例中，Mihai 可以将数组重新排列为 $[4, 1, 2, 3]$。然后过程如下：

• 第一个袋子有 $4$ 颗糖果，是偶数，所以 Mihai 拿走——此时 Mihai 有 $4$ 颗糖果，Bianca 有 $0$ 颗。
• 第二个袋子有 $1$ 颗糖果，是奇数，所以 Bianca 拿走——此时 Mihai 有 $4$ 颗糖果，Bianca 有 $1$ 颗。
• 第三个袋子有 $2$ 颗糖果，是偶数，所以 Mihai 拿走——此时 Mihai 有 $6$ 颗糖果，Bianca 有 $1$ 颗。
• 第四个袋子有 $3$ 颗糖果，是奇数，所以 Bianca 拿走——此时 Mihai 有 $6$ 颗糖果，Bianca 有 $4$ 颗。

由于 Mihai 始终拥有比 Bianca 更多的糖果，因此这种排列是可行的。

由 ChatGPT 4.1 翻译

来源

Codeforces 1807B，英文题名 Grab the Candies。