Problem Description

There is a sequence of length $n$. The weight of the $i$-th number is $a_i$. Two players, A and B, are playing a game. They will take turns performing operations on the sequence. Each player has two choices each turn:

• Delete any two numbers $a_i, a_j$ $(i \neq j)$ from the sequence, and add a new number with weight $a_i + a_j$ into the sequence. When there is only one number in the sequence, this operation cannot be performed.
• Take away one number from the sequence, add up the weights of all remaining numbers and give the total to the opponent, then end the game.

If A ends up with a larger total weight, then A wins; otherwise, B wins.

A moves first. Determine whether A has a winning strategy. It is guaranteed that the sum of $a_i$ is odd.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$ $(1\leq T\leq 10^5)$, denoting the number of test cases.

For each test case, the input format is as follows.

The first line contains an integer $n$ $(1\leq n\leq 5 \times 10^5)$, denoting the initial length of the sequence.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ $(1\leq a_i\leq 10^9)$, denoting the initial sequence.

It is guaranteed that $\sum n\leq 10^6$ and $\sum a_i$ is odd.

Output Format

For each test case, if A has a winning strategy, output YES; otherwise output NO.

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

NO
YES
NO

Hint

The explanation for Sample 1 is as follows:

• If A chooses the number with weight $3$, then the weight B can get is $6+4=10$.
• If A chooses the number with weight $4$, then the weight B can get is $3+6=9$.
• If A chooses the number with weight $6$, then the weight B can get is $3+4=7$.
• If A chooses to merge weights $3,6$, the sequence becomes $9,4$. If B chooses the number with weight $9$, then the weight A can get is $4$.
• If A chooses to merge weights $3,4$, the sequence becomes $7,6$. If B chooses the number with weight $7$, then the weight A can get is $6$.
• If A chooses to merge weights $4,6$, the sequence becomes $10,3$. If B chooses the number with weight $10$, then the weight A can get is $3$.

In all cases, B can obtain a higher total weight by playing optimally, so A cannot win.

The explanation for Sample 2 is as follows:

If A chooses the number with weight $2$, then the weight B can get is $1$.

Therefore, A has a winning strategy.

Translated by ChatGPT 5