CF1811C.Restore the Array

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:

1. Calculated $b_1 = \max(a_1, a_2) = \max(3, 0) = 3$;
2. Calculated $b_2 = \max(a_2, a_3) = \max(0, 4) = 4$;
3. Calculated $b_3 = \max(a_3, a_4) = \max(4, 0) = 4$;
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.

克里斯蒂娜有一个长度为 $n$ 的非负整数数组 $a$。

她构造了一个新数组 $b$，长度为 $n-1$，其中 $b_i = \max(a_i, a_{i+1})$（$1 \le i \le n-1$）。

例如，假设克里斯蒂娜最初的数组 $a = [3, 0, 4, 0, 5]$，长度为 $5$。那么她进行了如下操作：

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

最终得到数组 $b = [3, 4, 4, 5]$，长度为 $4$。

你仅知道数组 $b$。请找出任意一个可能的原始数组 $a$，使得由它按上述规则生成的数组恰好为 $b$。

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

输入数据的第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）—— Kristina 原始数组 $a$ 的元素个数。

每个测试用例的第二行包含恰好 $n-1$ 个非负整数 —— 数组 $b$ 的元素（$0 \le b_i \le 10^9$）。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$，且数组 $b$ 是由某个数组 $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.

对于每个测试用例，在单独的一行上，精确输出 $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$.

第一个测试用例在题目描述中已作解释。

在第二个测试用例中，我们可以从数组 $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$ 的所有元素均为零。由于每个 $b_i$ 都是数组 $a$ 中两个相邻元素的最大值，因此数组 $a$ 只能全部由零构成。

在第四个测试用例中，我们可以从数组 $a$ = [$0, 0, 3, 4, 3, 3$] 得到数组 $b$ = [$0, 3, 4, 4, 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$。