← 返回题目列表

Codeforces · 1811/C

C. 恢复阵列

中文机器翻译题面 查看原题

Kristina 有一个长度为 $$$n$$$ 的数组 $$$a$$$,由非负整数组成。

她构建了一个长度为 $$$n-1$$$ 的新数组 $$$b$$$,使得 $$$b_i = \max(a_i, a_{i+1})$$$ ($$$1 \le i \le n-1$$$)。

例如,假设 Kristina 有一个长度为 $$$5$$$ 的数组 $$$a$$$ = [$$$3, 0, 4, 0, 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$$$。查找 Kristina 最初可能拥有的任何匹配数组 $$$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$$$ 正确构建的。

输出

对于单独一行上的每个测试用例,精确打印 $$$n$$$ 非负整数 - Kristina 最初拥有的数组 $$$a$$$ 的元素。

如果有多个可能的答案 - 输出其中任何一个。

示例

输入 #1

11
5
3 4 4 5
4
2 2 1
5
0 0 0 0
6
0 3 4 4 3
2
10
4
3 3 3
5
4 2 5 5
4
3 3 3
4
2 1 0
3
4 4
6
8 1 3 5 10

输出 #1

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

注意

第一个测试用例在问题陈述中进行了解释。

在第二个测试用例中,我们可以从数组 $$$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$$$。