← 返回题目列表

Codeforces · 1442/A

A. 极限减法

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

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

您可以根据需要多次使用以下操作:选择任何整数 $$$1 \le k \le n$$$ 并执行以下两项操作之一:

- 将数组的第一个元素减 1 $$$k$$$。
- 将数组最后一个元素减 1 $$$k$$$。

例如,如果 $$$n=5$$$ 且 $$$a=[3,2,2,1,4]$$$,则您可以对其应用以下操作之一(下面并未列出所有可能的选项):

- 从数组的前两个元素递减。此操作后 $$$a=[2, 1, 2, 1, 4]$$$;
- 从数组的最后三个元素递减。此操作后 $$$a=[3, 2, 1, 0, 3]$$$;
- 从数组的前五个元素开始递减。此操作后 $$$a=[2, 1, 1, 0, 3]$$$;

确定是否可以通过应用一定次数的运算使数组的所有元素都等于 0。

输入

第一行包含一个正整数 $$$t$$$ ($$$1 \le t \le 30000$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例都以包含一个整数 $$$n$$$ ($$$1 \le n \le 30000$$$) 的行开始——数组中的元素数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1 \ldots a_n$$$ ($$$1 \le a_i \le 10^6$$$)。

所有测试用例的 $$$n$$$ 总和不超过 $$$30000$$$。

输出

对于每个测试用例,在单独的行上输出:

- 是,如果可以通过应用一定数量的运算使数组的所有元素等于零。
- 否,否则。

YES 和 NO 中的字母在任何情况下都可以输出。

示例

输入 #1

4
3
1 2 1
5
11 7 9 6 8
5
1 3 1 3 1
4
5 2 1 10

输出 #1

YES
YES
NO
YES