27536번 - Stone Arranging 2 서브태스크다국어

문제

JOI-kun has $N$ go stones. The stones are numbered from 1ドル$ to $N$. The color of each stone is an integer between 1ドル$ and 10ドル^9,ドル inclusive. In the beginning, the color of Stone $i$ (1ドル ≤ i ≤ N$) is $A_i$.

From now, JOI-kun will perform $N$ operations. He will put the stones on the table in a line. The operation $i$ (1ドル ≤ i ≤ N$) will be performed as follows:

1. JOI-kun will put Stone $i$ on the immediate right of Stone $i - 1$. However, when $i = 1,ドル JOI-kun will put Stone 1ドル$ on the table.
2. If there is a stone among Stones 1ドル,ドル 2ドル,ドル $\dots,ドル $i - 1$ whose current color is the same as Stone $i,ドル let $j$ be the maximum index of such stones, and JOI-kun will paint all of Stones $j + 1,ドル $j + 2,ドル $\dots,ドル $i - 1$ with the color $A_i$.

In order to confirm whether the operations are correctly performed, JOI-kun wants to know in advance the colors of the stones after all the operations are performed.

Given information of the go stones, write a program which determines the colors of the stones after the N operations are performed.

입력

Read the following data from the standard input.

$N$

$A_1$

$A_2$

$\vdots$

$A_N$

출력

Write $N$ lines to the standard output. The $i$-th line (1ドル ≤ i ≤ N$) should contain the color of Stone $i$ after the $N$ operations are performed.

제한

• 1ドル ≤ N ≤ 200,000円$.
• 1ドル ≤ A_i ≤ 10^9$ (1ドル ≤ i ≤ N$).
• Given values are all integers.

서브태스크

힌트