← 返回题目列表

Codeforces · 1815/A

A. Ian 和数组排序

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

为了感谢 Ian,Mary 向 Ian 赠送了一个长度为 $$$n$$$ 的数组 $$$a$$$。为了让自己看起来很聪明,他想通过执行以下有限多次操作来使数组按非递减顺序排列:他选择两个相邻元素 $$$a_i$$$ 和 $$$a_{i+1}$$$ ($$$1\le i\le n-1$$$),并将它们都增加 $$$1$$$ 或将它们都减少 $$$1$$$。请注意,数组的元素可以变为负数。

作为一个聪明人,你会注意到,有一些数组,Ian 无法使其成为非递减顺序!因此,您决定编写一个程序来确定是否可以使数组按非降序排列。

输入

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

每个测试用例的第一行由一个整数 $$$n$$$ ($$$2\le n\le 3\cdot10^5$$$) 组成 - 数组中的元素数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le 10^9$$$) — 数组 $$$a$$$ 的元素。

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

输出

对于每个测试用例,如果存在使数组不减的操作序列,则输出“YES”,否则输出“NO”。

您可以在任何情况下打印每个字母(例如,“YES”、“Yes”、“yes”、“yEs”都将被识别为肯定答案)。

示例

输入 #1

5
3
1 3 2
2
2 1
4
1 3 5 7
4
2 1 4 3
5
5 4 3 2 1

输出 #1

YES
NO
YES
NO
YES

注意

对于第一个测试用例,我们可以将 $$$a_2$$$ 和 $$$a_3$$$ 都增加 $$$1$$$。该数组现在为 $$$[1, 4, 3]$$$。

然后我们可以将 $$$a_1$$$ 和 $$$a_2$$$ 都减少 $$$1$$$。该数组现在为 $$$[0, 3, 3]$$$,按非降序排序。所以答案是“是”。

对于第二个测试用例,无论 Ian 如何执行操作,$$$a_1$$$ 始终大于 $$$a_2$$$。所以答案是“不”,伊恩不能假装聪明。

对于第三个测试用例,数组已经处于非递减顺序,因此 Ian 不需要执行任何操作。