CF1811C.Restore the Array
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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 bi=max(ai,ai+1) ( 1≤i≤n−1 ).
For example, suppose Kristina had an array a = [ 3,0,4,0,5 ] of length 5 . Then she did the following:
- Calculated b1=max(a1,a2)=max(3,0)=3 ;
- Calculated b2=max(a2,a3)=max(0,4)=4 ;
- Calculated b3=max(a3,a4)=max(4,0)=4 ;
- Calculated b4=max(a4,a5)=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≤t≤104 ) — the number of test cases.
The description of the test cases follows.
The first line of each test case contains one integer n ( 2≤n≤2⋅105 ) — 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≤bi≤109 ).
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 , 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.
输入输出样例
输入#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
说明/提示
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 ]:
- b1=max(a1,a2)=max(2,2)=2 ;
- b2=max(a2,a3)=max(2,1)=2 ;
- b3=max(a3,a4)=max(1,1)=1 .
In the third test case, all elements of the array b are zeros. Since each bi 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 ] :
- b1=max(a1,a2)=max(0,0)=0 ;
- b2=max(a2,a3)=max(0,3)=3 ;
- b3=max(a3,a4)=max(3,4)=4 ;
- b4=max(a4,a5)=max(4,3)=4 ;
- b5=max(a5,a6)=max(3,3)=3 .