← 返回题目列表

Codeforces · 2060/D

D. 减去最小排序

中文机器翻译题面 查看原题

给定一个由 $$$n$$$ 正整数组成的序列 $$$a$$$。

您可以执行以下操作任意次。

- 选择索引 $$$i$$$ ($$$1 \le i < n$$$),并从 $$$a_i$$$ 和 $$$a_{i+1}$$$ 中减去 $$$\min(a_i,a_{i+1})$$$。

确定是否可以通过使用任意次数的操作使序列不减。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$)。

每个测试用例的第二行包含 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

如果可以使序列不减,则在新行上打印“YES”。否则,在新行上打印“NO”。

任何情况下都可以输出答案。例如,字符串“yEs”、“yes”和“Yes”也将被识别为肯定响应。

示例

输入 #1

5
5
1 2 3 4 5
4
4 3 2 1
4
4 5 2 3
8
4 5 4 5 4 5 4 5
9
9 9 8 2 4 4 3 5 3

输出 #1

YES
NO
YES
YES
NO

注意

在第一个测试用例中,数组已经排序。

在第二个测试用例中,我们可以证明这是不可能的。

在第三个测试用例中,对 $$$i=1$$$ 执行操作后,数组变为 $$$[0,1,2,3]$$$,现在处于非递减顺序。