P2148 [SDOI2009] E&D

E and W play a game called `E&D`. The rules are as follows: There are $2n$ piles of stones on the table, numbered $1 \sim 2n$. For convenience, we regard pile $2k-1$ and pile $2k$ ($1 \le k \le n$) as one group. The number of stones in pile $i$ is a positive integer $S_i$. One split operation is defined as follows: choose any pile of stones and remove it from the table. Then split the other pile in the same group, take some stones from it, and place them at the removed position to form a new pile. After the operation, the number of stones in every pile must be greater than $0$. Obviously, the pile being split must contain at least $2$ stones. The two players alternate performing split operations. If, on a player's turn, all piles have exactly $1$ stone, then no move is possible and that player loses. E makes the first move. He wants to know whether there exists a strategy that guarantees he can defeat W. Therefore, he asks F (you) to tell him whether a winning strategy exists. For example, suppose initially there are $4$ piles with sizes $1,2,3,1$. E can choose to remove pile $1$, then split pile $2$ (he can only split off $1$ stone). Next, W can only remove pile $4$, then split pile $3$ into $1$ and $2$. Finally, it is E's turn; he can only remove the pile of size $1$ among the last two piles, and split the other into $1$ and $1$. Thus, when it is W's turn, all piles have size $1$, so he loses. Therefore, E has a winning strategy.

**There are multiple test cases in this problem.** The first line contains an integer $T$, the number of test cases. For each test case: The first line contains an integer $N$, the total number of piles on the table; here $N$ is the $2n$ from the problem description. The second line contains $N$ integers $S_{1 \dots N}$.

For each test case, if E has a winning strategy, output a single string `YES`; otherwise, output a single string `NO`.

For $20\%$ of the testdata, $N=2$. For another $20\%$ of the testdata, $N \le 4$, $S_i \le 50$. For $100\%$ of the testdata, $1 \le T \le 20$, $1 \le N \le 2 \times 10^4$ and $N$ is even, $1 \le S_i \le 2 \times 10^9$. Translated by ChatGPT 5