問題一覧 > 通常問題

No.318 Gaku Gaku Gaku Gaku Gaku

レベル : / AI推定難易度 : 1100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 232
作問者 : n_vip
お気に入りにしたユーザー ProblemId : 899 / 自分の提出
問題文最終更新日: 2026-06-25 08:02:36
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2015 (順位表) の他の問題:

Note

This problem was created as the problem for day 11 of Advent Calendar Contest Advent Calendar 2015.

Preamble (you can solve the problem without reading this)

In the string 豊橋技術科学大学, 「大」 is sandwiched between 「学」s, so shouldn't it become 豊橋技術科学学学?

— Allen (@chaos_phantom) October 23, 2015

学習院大学 becomes 学学学学学

— (v・∇)v {εぷりん.vvv] (@mat_der_D) October 23, 2015
I found these tweets amusing, so I am basing this problem on them. There was also this tweet:

大学院大学 becomes 大大大大学

— (v・∇)v {εぷりん.vvv] (@mat_der_D) October 23, 2015
However, in this case there are two each of 「大」 and 「学」, so depending on which one is processed first, the result can be either 大大大大学 or 大学学学学.
For that reason, I decided to assign priorities to the replacements. Assigning priorities to characters is a hassle, so I use a sequence of numbers instead of a string, and make it so that larger numbers tend to appear more often.

Problem Statement

You are given a sequence $a_1 ,\dots,a_n$. Based on this sequence, construct a sequence $b_1,\dots,b_n$ as follows.

For $t=1$ through $t=10^9$, in order, perform the following operation.
For all $l\le r$ such that $a_l=t$ , $a_r=t$, overwrite $b_l,\dots,b_r$ with $t$.

Find the sequence $b_1,\dots,b_n$.

Input

$n$
$a_1 \dots a_n$

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

Output

Print $b_1,\dots ,b_n$ on a single line, separated by spaces.

Sample

Sample 1
Input
6
3 2 1 1 2 3
Output
3 3 3 3 3 3

For convenience, assume that $\{b_n\}$ is initialized with 🎅.
After processing $t=1$, the sequence $\{b_n\}$ becomes $🎅,🎅,1,1,🎅,🎅$.
After processing $t=2$, the sequence $\{b_n\}$ becomes $🎅 ,2, 2, 2, 2, 🎅$.
After processing $t=3$, the sequence $\{b_n\}$ becomes $3 ,3, 3, 3, 3, 3$.
The operations for $t>3$ do not change the sequence $\{b_n\}$, so the answer is $3 ,3, 3, 3, 3, 3$.

Sample 2
Input
6
3 1 10 3 10 2
Output
3 3 10 10 10 2

After processing $t=1$, the sequence $\{b_n\}$ becomes $🎅,1,🎅,🎅,🎅,🎅$.
After processing $t=2$, the sequence $\{b_n\}$ becomes $🎅,1,🎅,🎅,🎅,2$.
After processing $t=3$, the sequence $\{b_n\}$ becomes $3,3,3,3,🎅,2$.
For $t=4, \dots ,9$, the sequence $\{b_n\}$ does not change.
After processing $t=10$, the sequence $\{b_n\}$ becomes $3,3,10,10,10,2$.
For $t>10$, the sequence $\{b_n\}$ does not change.

Sample 3
Input
6
1 3 10 1 10 2
Output
1 3 10 10 10 2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。