题目内容

实验台上有 $n$ 个试剂瓶排成一列，编号从 $1$ 到 $n$。第 $i$ 个瓶子的液面读数为整数 $w_i$，读数可以为负，表示该瓶当前欠量。

可以进行任意次（含零次）如下操作：选择一个长度为 $3$ 的连续区间 $[i, i+2]$（其中 $1 \le i \le n-2$），再任选一个实数 $x$（可正、可负、可为零），将三个瓶子的读数分别变为 $w_i - x$，$w_{i+1} + 2x$，$w_{i+2} - x$。

目标是使所有瓶子的读数均为非负数，即对所有 $1 \le i \le n$ 均有 $w_i \ge 0$。判断给定初始读数是否可能达成该目标。

约束：测试数据组数不超过 $10^4$。每组数据中瓶子数量不少于 $3$、不超过 $2 \times 10^5$。每个读数的绝对值不超过 $10^9$。单个测试文件中所有瓶子数量之和不超过 $2 \times 10^5$。

输入描述

第一行输入一个整数 $T$（$1 \le T \le 10^4$），表示测试数据组数。 对于每组测试数据： 第一行输入一个整数 $n$（$3 \le n \le 2 \times 10^5$），表示试剂瓶数量。 第二行输入 $n$ 个整数 $w_1, w_2, \ldots, w_n$（$-10^9 \le w_i \le 10^9$），表示各个瓶子的初始液面读数。 保证单个测试文件中所有 $n$ 之和不超过 $2 \times 10^5$。

输出描述

对于每组测试数据，输出一行：若能够通过若干次操作使所有瓶子的读数均为非负数，输出 YES；否则输出 NO。

样例1

输入

1
3
-1 2 -1

输出

YES

说明

按题意模拟计算得到。

样例2

输入

1
3
-1 2 -1
4

输出

YES

说明

按题意模拟计算得到。