310327: CF1816C. Ian and Array Sorting

C. Ian and Array Sortingtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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).

ExampleInput

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

Output

YES
NO
YES
NO
YES

Note

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.

题目大意：
Ian 收到了 Mary 赠送的一个长度为 n 的数组 a。Ian 想要通过有限次的操作将数组变为非递减顺序：他可以选择相邻的两个元素 a_i 和 a_{i+1}（1≤i≤n-1），并将它们都增加 1 或减少 1。注意，数组的元素可以变为负数。你需要写一个程序来确定是否有可能使数组变为非递减顺序。

输入数据格式：
第一行包含一个整数 t（1≤t≤10^4）——测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数 n（2≤n≤3×10^5）——数组中元素的数量。
第二行包含 n 个整数 a_1,a_2,…,a_n（1≤a_i≤10^9）——数组 a 的元素。
保证所有测试用例的 n 之和不超过 3×10^5。

输出数据格式：
对于每个测试用例，如果存在一系列操作使得数组变为非递减顺序，则输出 "YES"，否则输出 "NO"。
每个字母的大小写都可以（例如，"YES"、"Yes"、"yes"、"yEs" 都将被识别为肯定回答）。

示例：
输入：
5
3
1 3 2
2
2 1
4
1 3 5 7
4
2 1 4 3
5
5 4 3 2 1

输出：
YES
NO
YES
NO
YES

注意：
在第一个测试用例中，我们可以将 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 不需要做任何事情。题目大意： Ian 收到了 Mary 赠送的一个长度为 n 的数组 a。Ian 想要通过有限次的操作将数组变为非递减顺序：他可以选择相邻的两个元素 a_i 和 a_{i+1}（1≤i≤n-1），并将它们都增加 1 或减少 1。注意，数组的元素可以变为负数。你需要写一个程序来确定是否有可能使数组变为非递减顺序。 输入数据格式： 第一行包含一个整数 t（1≤t≤10^4）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 n（2≤n≤3×10^5）——数组中元素的数量。 第二行包含 n 个整数 a_1,a_2,…,a_n（1≤a_i≤10^9）——数组 a 的元素。 保证所有测试用例的 n 之和不超过 3×10^5。 输出数据格式： 对于每个测试用例，如果存在一系列操作使得数组变为非递减顺序，则输出 "YES"，否则输出 "NO"。 每个字母的大小写都可以（例如，"YES"、"Yes"、"yes"、"yEs" 都将被识别为肯定回答）。 示例： 输入： 5 3 1 3 2 2 2 1 4 1 3 5 7 4 2 1 4 3 5 5 4 3 2 1 输出： YES NO YES NO YES 注意： 在第一个测试用例中，我们可以将 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 不需要做任何事情。