問題文

ニワンゴくんは鉛筆を積むのが好きです。今日は以下の方法で鉛筆を積むことにしました。 まず、$N$本の鉛筆を左右に$1$列に床に並べます。左から$i$番目の鉛筆の長さは$L_i$です。

次に、$N-1$本の鉛筆を、床に並べた隣り合う$2$つの鉛筆の間の上に積みます。ただし、上に積む鉛筆の長さは、その下にある$2$つの鉛筆の長さのうち長い方と等しいです。すなわち、上に積む鉛筆のうち、左から$j$番目のものの長さを$K_j$と表すと、 $K_j=max\{L_j,L_{j+1}\}$ が成り立ちます。

例えば、上図のような鉛筆の積み方があります。ここで、円の中に書かれている数は鉛筆の長さを表します。

積んだ鉛筆を上から見たとき、上に積まれた$N-1$本の鉛筆の長さのみ見え、$N$本の土台にある鉛筆の長さは分かりません。この状態で、土台となる$N$本の鉛筆の長さとしてありうるものを考えるゲームをニワンゴくんは思いつきました。 あなたの仕事はこのゲームに正解するプログラムを書くことです。ただし、土台となる鉛筆の長さの組み合わせは存在することが保証されています。

すなわち、$N-1$個の数からなる数列$\{K_j\}$が与えられたとき、 $K_j=max\{L_j,L_{j+1}\} (1 ≦ j ≦ N-1)$がすべての$j$について成り立つような数列$\{L_i\}$を求めてください。

入力例1Copy

4
3 5 5

出力例1Copy

1 3 5 4

$1, 3, 5, 4$の長さの鉛筆を土台として$3$本の鉛筆を上に積むと、積まれた鉛筆の長さはそれぞれ$3, 5, 5$となることが分かります。よって、$1, 3, 5, 4$は答えの条件を満たします。

入力例2Copy

6
4 8 8 2 5

出力例2Copy

4 4 8 2 2 5

入力例3Copy

5
1 2 3 4

出力例3Copy

1 1 2 3 4