Grid Nim

While hiding out in the Outlands, Sam and Quorra get bored and start playing a game called grid nim, a complex variation on the classic game of nim. The board is a row of $n$ heaps, each holding a number of identical coins (see the figure). The two players move alternately.

On a move, a player takes the heap at either the left end or the right end of the row and removes it. There is one extra rule: a player may not take three consecutive heaps on three of their own consecutive turns. (This rule does not apply when only one heap is left at the end of the game.) The game ends when the board is empty.

The player who moves first wins if the total number of coins they collected is at least the total collected by the second player; otherwise the second player wins.

Here is one way the game might go for the board in the figure, assuming Sam moves first:

• Sam takes heap 1 from the left end (7 coins)
• Quorra takes heap 5 from the right end (5 coins)
• Sam takes heap 4 from the right end (3 coins)
• Quorra takes heap 3 from the right end (4 coins)
• Sam takes heap 2 (0 coins)

At the end Sam has $7 + 3 = 10$ coins, more than Quorra, so Sam wins. In fact Sam wins no matter what Quorra does: if she instead takes heap 2 (0 coins), Sam can take the heap with 5 coins and finish with a higher total of 15 or 16 coins.

The special rule does not come up in that example. Consider instead a board with many heaps and the opening moves:

Sam - Left, Quorra - Right, Sam - Left, Quorra - Right

On his next turn Sam may not take from the left end again, because that would be his third consecutive heap, so he must take from the right end:

Sam - Left, Quorra - Right, Sam - Left, Quorra - Right, Sam - Right

Now, even though Quorra took from the right end on her last two turns, she may still take from either end: because Sam just took from the right end, Quorra taking from the right would not be a third consecutive heap for her, so it is allowed.

Quorra plays perfectly and always makes the best possible move; to make it fair she lets Sam move first. Your task is to help Sam: given a starting board, determine whether Sam (moving first) has a winning strategy, assuming Quorra always plays optimally.

The first line contains the number of test cases $T$ (with $T \le 50$). Each of the following lines describes one test case: it starts with the number of heaps $k$, followed by $k$ integers giving the coin counts of the heaps from left to right. Every coin count is at least $0$ and less than $2^{30}$.

For each test case, print YES if Sam, moving first, has a winning strategy, or NO if he does not. Print each answer on its own line.