在清理海岸时,爱丽丝发现了 $$$n$$$ 堆石头。第 $$$i$$$ 堆有 $$$a_i$$$ 石头。
桩 $$$i$$$ 和 $$$i + 1$$$ 对于所有 $$$1 \leq i \leq n - 1$$$ 都是相邻的。如果堆 $$$i$$$ 变空,则堆 $$$i - 1$$$ 和 $$$i + 1$$$ 不会成为相邻堆。
爱丽丝懒得移除这些石头,所以她让你承担这个职责。她只允许你进行以下操作:
- 选择两个相邻的堆,如果它们都不是空的,则从每个堆中移走一颗石头。
爱丽丝明白,有时不可能通过给定的操作移除所有石头,因此她允许你使用以下超能力:
- 在开始清理之前,您可以选择两个相邻的桩并交换它们。
确定是否可以使用超级能力不超过一次移除所有石子。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含单个整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — 堆的数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 每堆石子的数量。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印“是”或“否”——是否可以使用超级能力不超过一次移除所有石头。
示例
输入 #1
5 3 1 2 1 3 1 1 2 5 2 2 2 1 3 5 2100 1900 1600 3000 1600 2 2443 2445
输出 #1
YES YES YES YES NO
注意
在第一个测试用例中,您可以在不使用超级能力的情况下移除所有石头:$$$[1, 2, 1] \rightarrow [1, 1, 0] \rightarrow [0, 0, 0]$$$。
在第二个测试用例中,您可以将超级能力应用于第二个和第三个桩,然后像第一个测试用例一样操作。
在第三个测试用例中,您可以将超能力应用于第四堆和第五堆,从而得到 $$$a = [2, 2, 2, 3, 1]$$$。
在第四个测试用例中,您可以将超能力应用于第一堆和第二堆,从而得到 $$$a = [1900, 2100, 1600, 3000, 1600]$$$。