给定一个由 $$$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