题目内容

Tk 有一堵防护墙，这堵墙有 $n$ 个信标。这些信标排成一列，编号从 $1$ 到 $n$。

每座信标都拥有一个“时序权重”，第 $i$ 座信标的权重初始值为 $w_i$。

为了重新激活这堵防护墙，Tk 需要对这些信标进行“时序重构”。重构的规则非常特殊，Tk 可以进行以下操作任意次，包括零次：

• 选择一个长度为 3 的连续子区间 $[i,i+2]$，其中 $1\leq i\leq n-2$；
• 任意选择一个实数 $x$，将该区间内三个信标的权重分别变为

$w_i-x,\qquad w_{i+1}+2x,\qquad w_{i+2}-x.$

其中，(x) 可以是正数、负数或零。

Tk 的目标是：通过若干次操作，使得所有信标的权重全部变为非负数，即对于所有 $1\leq i\leq n$，均满足

请你判断：给定初始的权重序列，Tk 是否有可能完成重构目标？

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数 $T$，表示测试数据的组数。截图中给出的范围为

对于每组测试数据：

第一行输入一个整数 (n)，表示时序信标的数量。截图中给出的范围为

第二行输入 (n) 个整数

表示各个信标的初始时序权重。$-10^9 \leq w_i \leq 10^9$

保证单个测试文件中所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

输出描述

对于每组测试数据，输出一行：

• 如果 Tk 能够通过若干次操作，使所有信标的权重均为非负数，输出 YES；
• 否则输出 NO。

样例1

输入

4
3
-1 2 -1
4
1 -1 0 1
3
-1 0 0
5
-3 0 0 0 4

输出

YES
YES
NO
NO