CF1811C Restore the Array

Kristina 有一个包含 $ n $ 个**非负整数**的数组 $ a $。 她构造了一个长度为 $ n - 1 $ 的新数组 $ b $，使得 $ b_i = \max(a_i, a_{i + 1}) \text{ } (1 \le i \le n - 1) $。 例如，假设 Kristina 有一个长度为 $ 5 $ 的数组 $ a = [ 3, 0, 4, 0, 5 ] $，则她将以以下方式构造数组 $ b $： 1. $ b_1 = \max(a_1, a_2) = \max(3, 0) = 3; $ 2. $ b_2 = \max(a_2, a_3) = \max(0, 4) = 4; $ 3. $ b_3 = \max(a_3, a_4) = \max(4, 0) = 4; $ 4. $ b_4 = \max(a_4, a_5) = \max(0, 5) = 5. $ 所以，她得到了一个长度为 $ 4 $ 的数组 $ b = [ 3, 4, 4, 5 ] $。 现在，你只知道数组 $ b $。你需要找出**任意一个**可能的数组 $ a $。 对于第二组测试数据，我们可以从 $ a = [ 2, 2, 1, 1 ] $ 推出 $ b = [ 2, 2, 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. $ 对于第三组测试数据，数组 $ b $ 中的所有元素均为 $ 0 $，因为 $ b $ 中的每个元素均为 $ a $ 中两个相邻元素的最大值，所以数组 $ a $ 中的每个元素均为 $ 0 $。 对于第四组测试数据，我们可以从 $ a = [ 0, 0, 3, 4, 3, 3 ] $ 推出 $ b = [ 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. $

输入数据的第一行包含一个整数 $ t \text{ } (1 \le t \le 10 ^ 4) $，代表测试数据组数。 每组测试数据的第一行包含一个整数 $ n \text{ } (1 \le n \le 2 \times 10 ^ 5) $，代表数组 $ a $ 的长度。 每组测试数据的第二行包含 $ n - 1 $ 个非负整数，代表数组 $ b $ 的各个元素 $ (0 \le b_i \le 10^9) $。 对于每个测试点，保证所有 $ t $ 组测试数据中 $ n $ 的总和不超过 $ 2 \times 10 ^ 5 $，且保证有解。

对于每组测试数据，在同一行内输出 $ n $ 个非负整数，代表数组 $ a $ 的元素，元素与元素之间以空格隔开。 如果有多种可能的答案，输出**任意一种**即可。

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 $ .