No.318 学学学学学

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 96
作問者 : n_vipn_vip

7 ProblemId : 899 / 出題時の順位表

Note

この問題はAdvent Calendar Contest Advent Calendar 2015の11日目の問題として作られました。

前置き(読まなくても解けます)

豊橋技術科学大学って文字列、「大」が「学」に挟まれてるんだから豊橋技術科学学学になるべきでは?

— アレン (@chaos_phantom) 2015, 10月 23

学習院大学は学学学学学に

— (v・∇)v {εぷりん.vvv] (@mat_der_D) 2015, 10月 23
このツイートが面白いと思ったのでこれで出題します。この他にも

大学院大学は大大大大学に

— (v・∇)v {εぷりん.vvv] (@mat_der_D) 2015, 10月 23
というツイートもありました。 ただ、この場合「大」と「学」がそれぞれ2つずつあるので、どっちを先にやるかによって大大大大学にも大学学学学にもなってしまいます。
そのため、置き換える優先順位をつけることにしました。文字に優先順位をつけるのはめんどくさいので、 文字列の代わりに数列にして、数が大きい方が多く出てきやすくなるようにします。

問題文

数列 $a_1 ,\dots,a_n$ が与えられます。この数列を元に数列 $b_1,\dots,b_n$ を次のように作ります。

$t=1$ から $t=10^9$ について、順番に次の操作をする。
$a_l=t$ , $a_r=t$ であるような全ての $l\le r$ について、$b_l,\dots,b_r$ を $t$ で書き換える。

数列 $b_1,\dots,b_n$ を求めて下さい。

入力

$n$
$a_1 \dots a_n$

$1\le n\le 10^5$
$1\le a_i\le 10^9$

出力

$b_1,\dots ,b_n$ を空白区切りで一行に出力して下さい。

サンプル

サンプル1
入力
6
3 2 1 1 2 3
出力
3 3 3 3 3 3

便宜上$\{b_n\}$が🎅で初期化されているとします。
$t=1$について処理をすると、数列$\{b_n\}$は $🎅,🎅,1,1,🎅,🎅$ となります。
$t=2$について処理をすると、数列$\{b_n\}$は $🎅 ,2, 2, 2, 2, 🎅$ となります。
$t=3$について処理をすると、数列$\{b_n\}$は $3 ,3, 3, 3, 3, 3$ となります。
$t>3$の操作では数列$\{b_n\}$は変化しないので、答えは$3 ,3, 3, 3, 3, 3$です。

サンプル2
入力
6
3 1 10 3 10 2
出力
3 3 10 10 10 2

$t=1$について処理をすると、数列$\{b_n\}$は $🎅,1,🎅,🎅,🎅,🎅$ となります。
$t=2$について処理をすると、数列$\{b_n\}$は $🎅,1,🎅,🎅,🎅,2$ となります。
$t=3$について処理をすると、数列$\{b_n\}$は $3,3,3,3,🎅,2$ となります。
$t=4, \dots ,9$では数列$\{b_n\}$は変化しません。
$t=10$について処理をすると、数列$\{b_n\}$は $3,3,10,10,10,2$ となります。
$t>10$では数列$\{b_n\}$は変化しません。

サンプル3
入力
6
1 3 10 1 10 2
出力
1 3 10 10 10 2

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。