Restore the Array (Codeforces 1811C)
Tags: Greedy, constructive algorithms

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

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

Output: 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.

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

Sample Inputs:
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

Sample Outputs:
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

Solution (Python):
def solve():
    n = int(input())
    b = [int(x) for x in input().split()]
    a = [0] * n
    a[0] = b[0]
    a[n - 1] = b[n - 2]
    for i in range(1, n - 1):
        bp = b[i - 1]
        bc = b[i]
        a[i] = bp if bp < bc else bc
    print(' '.join([str(x) for x in a]))
numc = int(input())
while numc:
    numc -= 1
    solve()

Solution (Python):
def main():
    for t in range(int(input())):
        n = int(input()) - 1
        b = list(map(int, input().split()))
        arr = [b[0]]
        for k in range(n - 1):
            arr += [min(b[k], b[k + 1])]
        arr += [b[-1]]
        print(' '.join(list(map(str, arr))))
if __name__ == '__main__':
    main()

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    b = [0] * n
    b[0] = arr[0]
    b[-1] = arr[-1]
    for i in range(1, n - 1):
        b[i] = min(arr[i], arr[i - 1])
    b = (str(x) for x in b)
    b = ' '.join(b)
    print(b)