Problem Description

Niwango-kun loves stacking pencils. Today, he decided to stack pencils in the following way: First, he arranges $N$ pencils in a single row on the floor, from left to right. The length of the $i$-th pencil from the left is $L_i$.

Next, he stacks $N-1$ pencils on top of the pairs of adjacent pencils on the floor. The length of each pencil placed on top is equal to the longer of the two pencils beneath it. That is, if we denote the length of the $j$-th pencil on top as $K_j$, then $K_j = \max\{L_j, L_{j+1}\}$ holds.

For example, the figure below shows one way of stacking pencils. The numbers written inside the circles represent the lengths of the pencils.

When viewed from above, only the lengths of the $N-1$ stacked pencils are visible, and the lengths of the $N$ base pencils are not visible. Niwango-kun came up with a game to consider possible lengths of the $N$ base pencils. Your task is to write a program to solve this game. It is guaranteed that a combination of lengths for the base pencils exists.

That is, given a sequence of $N-1$ numbers $\{K_j\}$, find a sequence $\{L_i\}$ such that $K_j = \max\{L_j, L_{j+1}\}$ for all $j$.

Input & Output Format

The input is given from the standard input in the following format:

$N$ $K_1$ $K_2$ … $K_{N-1}$

• The first line contains the number of base pencils $N$ ($2 \leq N \leq 10^5$).
• The second line contains $N-1$ integers $K_1, ..., K_{N-1}$ representing the lengths of the stacked pencils, separated by spaces.
• $1 \leq K_i \leq 10^9$ ($1 \leq i \leq N$) holds.

Input Format

None

Output Format

Output the lengths of the base pencils $L_1, ..., L_N$ separated by spaces in one line. Include a newline at the end of the output.

Sample Input and Output

Sample Input #1

4
3 5 5

Sample Output #1

1 3 5 4

Sample Input #2

6
4 8 8 2 5

Sample Output #2

4 4 8 2 2 5

Sample Input #3

5
1 2 3 4

Sample Output #3

1 1 2 3 4

Notes/Hints

Sample Explanation 1

If the base pencils have lengths $1, 3, 5, 4$, and we stack 3 pencils on top, the lengths of the stacked pencils will be $3, 5, 5$, respectively. Therefore, $1, 3, 5, 4$ satisfies the condition of the answer.

见题面 Input 部分

见题面 Output 部分