C. Restore the Array
constructive algorithms; greedy
Kristina had an array \(a\) of length \(n\) consisting of non-negative integers.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\)).For example, suppose Kristina had an array \(a\) = [\(3, 0, 4, 0, 5\)] of length \(5\). Then she did the following: Calculated \(b_1 = \max(a_1, a_2) = \max(3, 0) = 3\); Calculated \(b_2 = \max(a_2, a_3) = \max(0, 4) = 4\); Calculated \(b_3 = \max(a_3, a_4) = \max(4, 0) = 4\); Calculated \(b_4 = \max(a_4, a_5) = \max(0, 5) = 5\). As a result, she got an array \(b\) = [\(3, 4, 4, 5\)] of length \(4\).You only know the array \(b\). Find any matching array \(a\) that Kristina may have originally had.
The first line of input data contains a single integer \(t\) (\(1 \le t \le 10^4\)) — the number of test cases.The description of the test cases follows.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.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\)).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\).
For each test case on a separate line, print exactly \(n\) non-negative integers — the elements of the array \(a\) that Kristina originally had.If there are several possible answers — output any of them.
The first test case is explained in the problem statement.In the second test case, we can get array \(b\) = [\(2, 2, 1\)] from the array \(a\) = [\(2, 2, 1, 1\)]: \(b_1 = \max(a_1, a_2) = \max(2, 2) = 2\); \(b_2 = \max(a_2, a_3) = \max(2, 1) = 2\); \(b_3 = \max(a_3, a_4) = \max(1, 1) = 1\). 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.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\)] : \(b_1 = \max(a_1, a_2) = \max(0, 0) = 0\); \(b_2 = \max(a_2, a_3) = \max(0, 3) = 3\); \(b_3 = \max(a_3, a_4) = \max(3, 4) = 4\); \(b_4 = \max(a_4, a_5) = \max(4, 3) = 4\); \(b_5 = \max(a_5, a_6) = \max(3, 3) = 3\).