Codeforces Round 863 (Div. 3) |
---|
Finished |
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:
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.
1153 4 4 542 2 150 0 0 060 3 4 4 321043 3 354 2 5 543 3 342 1 034 468 1 3 5 10
3 0 4 0 5 2 2 1 1 0 0 0 0 0 0 0 3 4 3 3 10 10 3 3 3 1 4 2 2 5 5 3 3 3 3 2 1 0 0 2 4 4 8 1 1 3 5 10
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$$$]:
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$$$] :
Name |
---|