Stone Arranging 2

문제

JOI-kun has $NN$ go stones. The stones are numbered from $11$ to $NN$. The color of each stone is an integer between $11$ and ${10}^{9}10^9$, inclusive. In the beginning, the color of Stone $ii$ (1 ≤ i ≤ N) is $A_{i}A\_i$.

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

1. JOI-kun will put Stone $ii$ on the immediate right of Stone $i-1i\; -\; 1$. However, when $i=1i\; =\; 1$, JOI-kun will put Stone $11$ on the table.
2. If there is a stone among Stones $11$, $22$, $\dots \backslash dots$, $i-1i\; -\; 1$ whose current color is the same as Stone $ii$, let $jj$ be the maximum index of such stones, and JOI-kun will paint all of Stones $j+1j\; +\; 1$, $j+2j\; +\; 2$, $\dots \backslash dots$, $i-1i\; -\; 1$ with the color $A_{i}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.

$NN$

$A_{1}A\_1$

$A_{2}A\_2$

$\mathrm{⋮}\backslash vdots$

$A_{N}A\_N$

출력

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

6
1
2
1
2
3
2

1
1
1
2
2
2

10
1
1
2
2
1
2
2
1
1
2

1
1
1
1
1
1
1
1
1
2