310265: CF1807B. Grab the Candies

B. Grab the Candiestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Mihai and Bianca are playing with bags of candies. They have a row $a$ of $n$ bags of candies. The $i$-th bag has $a_i$ candies. The bags are given to the players in the order from the first bag to the $n$-th bag.

If a bag has an even number of candies, Mihai grabs the bag. Otherwise, Bianca grabs the bag. Once a bag is grabbed, the number of candies in it gets added to the total number of candies of the player that took it.

Mihai wants to show off, so he wants to reorder the array so that at any moment (except at the start when they both have no candies), Mihai will have strictly more candies than Bianca. Help Mihai find out if such a reordering exists.

Input

The first line of the input contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 100$) — the number of bags in the array.

The second line of each test case contains $n$ space-separated integers $a_i$ ($1 \leq a_i \leq 100$) — the number of candies in each bag.

Output

For each test case, output "YES" (without quotes) if such a reordering exists, and "NO" (without quotes) otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

ExampleInput

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

Output

YES
NO
NO

Note

In the first test case, Mihai can reorder the array as follows: $[4, 1, 2, 3]$. Then the process proceeds as follows:

• the first bag has $4$ candies, which is even, so Mihai takes it — Mihai has $4$ candies, and Bianca has $0$.
• the second bag has $1$ candies, which is odd, so Bianca takes it — Mihai has $4$ candies, and Bianca has $1$.
• the third bag has $2$ candies, which is even, so Mihai takes it — Mihai has $6$ candies, and Bianca has $1$.
• the fourth bag has $3$ candies, which is odd, so Bianca takes it — Mihai has $6$ candies, and Bianca has $4$.

Since Mihai always has more candies than Bianca, this reordering works.

题目大意：
Mihai和Bianca在玩抢糖果游戏。有一排共有n个装糖果的袋子，第i个袋子里有a_i个糖果。按照从第一个袋子到第n个袋子的顺序给玩家。如果袋子里的糖果是偶数，Mihai拿走袋子；如果是奇数，Bianca拿走。一旦袋子被拿走，里面的糖果数量就加到拿走它的玩家的糖果总数上。Mihai想要炫耀，他想要重新排列这个数组，以便在任何时刻（除了开始时他们都没有糖果的时候），Mihai的糖果数量都严格多于Bianca。帮助Mihai找出是否存在这样的重新排列。

输入数据格式：
输入的第一行包含一个整数t（1≤t≤1000）——测试用例的数量。
每个测试用例的第一行包含一个整数n（1≤n≤100）——数组中的袋子数量。
每个测试用例的第二行包含n个空格分隔的整数a_i（1≤a_i≤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的糖果多，这种重新排列是有效的。题目大意： Mihai和Bianca在玩抢糖果游戏。有一排共有n个装糖果的袋子，第i个袋子里有a_i个糖果。按照从第一个袋子到第n个袋子的顺序给玩家。如果袋子里的糖果是偶数，Mihai拿走袋子；如果是奇数，Bianca拿走。一旦袋子被拿走，里面的糖果数量就加到拿走它的玩家的糖果总数上。Mihai想要炫耀，他想要重新排列这个数组，以便在任何时刻（除了开始时他们都没有糖果的时候），Mihai的糖果数量都严格多于Bianca。帮助Mihai找出是否存在这样的重新排列。 输入数据格式： 输入的第一行包含一个整数t（1≤t≤1000）——测试用例的数量。 每个测试用例的第一行包含一个整数n（1≤n≤100）——数组中的袋子数量。 每个测试用例的第二行包含n个空格分隔的整数a_i（1≤a_i≤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的糖果多，这种重新排列是有效的。