1674D.md (2611B)
1 Source: https://codeforces.com/problemset/problem/1674/D 2 3 D. A-B-C Sort 4 5 time limit per test 6 7 2 seconds 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 You are given three arrays $a$, $b$ and $c$. Initially, array $a$ consists of $n$ elements, arrays $b$ and $c$ are empty. 22 23 You are performing the following algorithm that consists of two steps: 24 25 * Step $1$: while $a$ is not empty, you take the last element from $a$ and move it in the middle of array $b$. If $b$ currently has odd length, you can choose: place the element from $a$ to the left or to the right of the middle element of $b$. As a result, $a$ becomes empty and $b$ consists of $n$ elements. 26 * Step $2$: while $b$ is not empty, you take the middle element from $b$ and move it to the end of array $c$. If $b$ currently has even length, you can choose which of two middle elements to take. As a result, $b$ becomes empty and $c$ now consists of $n$ elements. 27 28 Refer to the Note section for examples. 29 30 Can you make array $c$ sorted in non-decreasing order? 31 32 Input 33 34 The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Next $t$ cases follow. 35 36 The first line of each test case contains the single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of array $a$. 37 38 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — the array $a$ itself. 39 40 It's guaranteed that the sum of $n$ doesn't exceed $2 \cdot 10^5$. 41 42 Output 43 44 For each test, print YES (case-insensitive), if you can make array $c$ sorted in non-decreasing order. Otherwise, print NO (case-insensitive). 45 46 Example 47 48 Input 49 50 ``` 51 3 52 53 4 54 55 3 1 5 3 56 57 3 58 59 3 2 1 60 61 1 62 63 7331 64 ``` 65 66 Output 67 68 ``` 69 YES 70 NO 71 YES 72 ``` 73 74 Note 75 76 In the first test case, we can do the following for $a = [3, 1, 5, 3]$: 77 78 Step $1$: 79 80 | | | | | | | | | | | 81 | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | 82 | $a$ | $[3, 1, 5, 3]$ | $\Rightarrow$ | $[3, 1, 5]$ | $\Rightarrow$ | $[3, 1]$ | $\Rightarrow$ | $[3]$ | $\Rightarrow$ | $[]$ | 83 | $b$ | $[]$ | | $[\underline{3}]$ | | $[3, \underline{5}]$ | | $[3, \underline{1}, 5]$ | | $[3, \underline{3}, 1, 5]$ | 84 85 Step $2$: 86 87 | | | | | | | | | | | 88 | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | 89 | $b$ | $[3, 3, \underline{1}, 5]$ | $\Rightarrow$ | $[3, \underline{3}, 5]$ | $\Rightarrow$ | $[\underline{3}, 5]$ | $\Rightarrow$ | $[\underline{5}]$ | $\Rightarrow$ | $[]$ | 90 | $c$ | $[]$ | | $[1]$ | | $[1, 3]$ | | $[1, 3, 3]$ | | $[1, 3, 3, 5]$ | 91 92 As a result, array $c = [1, 3, 3, 5]$ and it's sorted.