第2回 ドワンゴからの挑戦状 予選

B - 積み鉛筆


Time limit時間制限 : 2.525sec / Memory limitメモリ制限 : 252.525MB

問題文

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

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

https://discovery2016-qual.contest.atcoder.jp/img/other/dwango2016qual/hdfksjghkjsdfhgkjsdhfgkjs/problem4.PNG

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

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

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


入出力

入力は以下の形式で標準入力から与えられる。

N
K_1 K_2K_{N-1}
  • 1 行目には、土台となる鉛筆の本数 N (2 ≦ N ≦ 10^5)が与えられる。
  • 2 行目には、上に積まれている鉛筆の長さを表すN-1個の整数K_1,...,K_{N-1}が空白区切りで与えられる。
  • 1 ≦ K_i ≦ 10^9(1 ≦ i ≦ N)が成り立つ。

出力

土台となる鉛筆の長さL_1,...,L_Nを空白区切りで1行に出力せよ。出力の末尾には改行をいれること。


入力例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

Submit提出する