CF1815A.Ian and Array Sorting

To thank Ian, Mary gifted an array $a$ of length $n$ to Ian. To make himself look smart, he wants to make the array in non-decreasing order by doing the following finitely many times: he chooses two adjacent elements $a_i$ and $a_{i+1}$ ($1\le i\le n-1$), and increases both of them by $1$ or decreases both of them by $1$. Note that, the elements of the array can become negative.

As a smart person, you notice that, there are some arrays such that Ian cannot make it become non-decreasing order! Therefore, you decide to write a program to determine if it is possible to make the array in non-decreasing order.

为了感谢 Ian，Mary 赠送了一个长度为 $n$ 的数组 $a$ 给 Ian。为了显得聪明，Ian 希望通过有限次如下操作，将该数组变为非递减序列：他选择两个相邻元素 $a_i$ 和 $a_{i+1}$（其中 $1\le i\le n-1$），并将这两个元素同时加 $1$ 或同时减 $1$。注意，数组中的元素可以变为负数。

作为一名聪明的人，你注意到：存在一些数组，Ian 无法通过上述操作将其变为非递减序列！因此，你决定编写一个程序来判断：是否可能通过上述操作使该数组变为非递减序列。

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of test cases follows.

The first line of each test case consists of a single integer $n$ ($2\le n\le 3\cdot10^5$) — the number of elements in the array.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^9$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot10^5$.

第一行包含一个整数 $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$。

For each test case, output "YES" if there exists a sequence of operations which make the array non-decreasing, else output "NO".

You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).

对于每个测试用例，如果存在一系列操作使得数组变为非递减的，则输出 “YES”，否则输出 “NO”。

您可以以任意大小写形式输出每个字母（例如，“YES”、“Yes”、“yes”、“yEs” 均会被识别为肯定回答）。

For the first test case, we can increase $a_2$ and $a_3$ both by $1$. The array is now $[1, 4, 3]$.

Then we can decrease $a_1$ and $a_2$ both by $1$. The array is now $[0, 3, 3]$, which is sorted in non-decreasing order. So the answer is "YES".

For the second test case, no matter how Ian perform the operations, $a_1$ will always be larger than $a_2$. So the answer is "NO" and Ian cannot pretend to be smart.

For the third test case, the array is already in non-decreasing order, so Ian does not need to do anything.

对于第一个测试用例，我们可以将 $a_2$ 和 $a_3$ 同时增加 $1$。此时数组变为 $[1, 4, 3]$。

接着，我们可以将 $a_1$ 和 $a_2$ 同时减少 $1$。此时数组变为 $[0, 3, 3]$，已按非递减顺序排列。因此答案为 “YES”。

对于第二个测试用例，无论 Ian 如何执行操作，$a_1$ 始终会大于 $a_2$。因此答案为 “NO”，Ian 无法假装聪明。

对于第三个测试用例，数组本身已处于非递减顺序，因此 Ian 无需进行任何操作。