問題文

ニワンゴくんは鉛筆を積むのが好きです。今日は以下の方法で鉛筆を積むことにしました。 まず、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\}を求めてください。

入力例1

4
3 5 5

出力例1

1 3 5 4

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

入力例2

6
4 8 8 2 5

出力例2

4 4 8 2 2 5

入力例3

5
1 2 3 4

出力例3

1 1 2 3 4