1811C.md (2759B)
1 Source: https://codeforces.com/problemset/problem/1811/C 2 3 C. Restore the Array 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 Kristina had an array $a$ of length $n$ consisting of non-negative integers. 22 23 She built a new array $b$ of length $n-1$, such that $b_i = \max(a_i, a_{i+1})$ ($1 \le i \le n-1$). 24 25 For example, suppose Kristina had an array $a$ = [$3, 0, 4, 0, 5$] of length $5$. Then she did the following: 26 27 1. Calculated $b_1 = \max(a_1, a_2) = \max(3, 0) = 3$; 28 2. Calculated $b_2 = \max(a_2, a_3) = \max(0, 4) = 4$; 29 3. Calculated $b_3 = \max(a_3, a_4) = \max(4, 0) = 4$; 30 4. Calculated $b_4 = \max(a_4, a_5) = \max(0, 5) = 5$. 31 32 As a result, she got an array $b$ = [$3, 4, 4, 5$] of length $4$. 33 34 You only know the array $b$. Find any matching array $a$ that Kristina may have originally had. 35 36 Input 37 38 The first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 39 40 The description of the test cases follows. 41 42 The first line of each test case contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of elements in the array $a$ that Kristina originally had. 43 44 The second line of each test case contains exactly $n-1$ non-negative integer — elements of array $b$ ($0 \le b_i \le 10^9$). 45 46 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$, and that array $b$ was built correctly from some array $a$. 47 48 Output 49 50 For each test case on a separate line, print exactly $n$ non-negative integers — the elements of the array $a$ that Kristina originally had. 51 52 If there are several possible answers — output any of them. 53 54 Example 55 56 Input 57 58 ``` 59 11 60 61 5 62 63 3 4 4 5 64 65 4 66 67 2 2 1 68 69 5 70 71 0 0 0 0 72 73 6 74 75 0 3 4 4 3 76 77 2 78 79 10 80 81 4 82 83 3 3 3 84 85 5 86 87 4 2 5 5 88 89 4 90 91 3 3 3 92 93 4 94 95 2 1 0 96 97 3 98 99 4 4 100 101 6 102 103 8 1 3 5 10 104 ``` 105 106 Output 107 108 ``` 109 3 0 4 0 5 110 2 2 1 1 111 0 0 0 0 0 112 0 0 3 4 3 3 113 10 10 114 3 3 3 1 115 4 2 2 5 5 116 3 3 3 3 117 2 1 0 0 118 2 4 4 119 8 1 1 3 5 10 120 ``` 121 122 Note 123 124 The first test case is explained in the problem statement. 125 126 In the second test case, we can get array $b$ = [$2, 2, 1$] from the array $a$ = [$2, 2, 1, 1$]: 127 128 * $b_1 = \max(a_1, a_2) = \max(2, 2) = 2$; 129 * $b_2 = \max(a_2, a_3) = \max(2, 1) = 2$; 130 * $b_3 = \max(a_3, a_4) = \max(1, 1) = 1$. 131 132 In the third test case, all elements of the array $b$ are zeros. Since each $b_i$ is the maximum of two adjacent elements of array $a$, array $a$ can only consist entirely of zeros. 133 134 In the fourth test case, we can get array $b$ = [$0, 3, 4, 4, 3$] from the array $a$ = [$0, 0, 3, 4, 3, 3$] : 135 136 * $b_1 = \max(a_1, a_2) = \max(0, 0) = 0$; 137 * $b_2 = \max(a_2, a_3) = \max(0, 3) = 3$; 138 * $b_3 = \max(a_3, a_4) = \max(3, 4) = 4$; 139 * $b_4 = \max(a_4, a_5) = \max(4, 3) = 4$; 140 * $b_5 = \max(a_5, a_6) = \max(3, 3) = 3$.