1815A.md (2224B)
1 Source: https://codeforces.com/problemset/problem/1815/A 2 3 A. Ian and Array Sorting 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 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. 24 25 Input 26 27 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. 28 29 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. 30 31 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$. 32 33 It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot10^5$. 34 35 Output 36 37 For each test case, output "YES" if there exists a sequence of operations which make the array non-decreasing, else output "NO". 38 39 You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer). 40 41 Example 42 43 Input 44 45 ``` 46 5 47 48 3 49 50 1 3 2 51 52 2 53 54 2 1 55 56 4 57 58 1 3 5 7 59 60 4 61 62 2 1 4 3 63 64 5 65 66 5 4 3 2 1 67 ``` 68 69 Output 70 71 ``` 72 YES 73 NO 74 YES 75 NO 76 YES 77 ``` 78 79 Note 80 81 For the first test case, we can increase $a_2$ and $a_3$ both by $1$. The array is now $[1, 4, 3]$. 82 83 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". 84 85 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. 86 87 For the third test case, the array is already in non-decreasing order, so Ian does not need to do anything.