No.318 学学学学学
n_vipNote
この問題はAdvent Calendar Contest Advent Calendar 2015の11日目の問題として作られました。前置き（読まなくても解けます）
豊橋技術科学大学って文字列、「大」が「学」に挟まれてるんだから豊橋技術科学学学になるべきでは？
— アレン (@chaos_phantom) 2015, 10月 23
このツイートが面白いと思ったのでこれで出題します。この他にも学習院大学は学学学学学に
— (v・∇)v {εぷりん.vvv] (@mat_der_D) 2015, 10月 23
というツイートもありました。 ただ、この場合「大」と「学」がそれぞれ2つずつあるので、どっちを先にやるかによって大大大大学にも大学学学学にもなってしまいます。大学院大学は大大大大学に
— (v・∇)v {εぷりん.vvv] (@mat_der_D) 2015, 10月 23
そのため、置き換える優先順位をつけることにしました。文字に優先順位をつけるのはめんどくさいので、 文字列の代わりに数列にして、数が大きい方が多く出てきやすくなるようにします。
問題文
数列 $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
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。