시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB37212170.000%

## 문제

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.

## 서브태스크

번호배점제한
125

$N ≤ 2\,000$.

235

$A_i ≤ 2$ ($1 ≤ i ≤ N$).

340

## 예제 입력 1

6
1
2
1
2
3
2


## 예제 출력 1

1
1
1
2
2
2


The operations are performed as in the following table.

Operation The colors of the stones on the table Explanation
$1$ $1$ Stone $1$ is put on the table.
$2$ $1, 2$ Stone $2$ is put on the immediate right of Stone $1$.
$3$ $1, 2, 1$ Stone $3$ is put on the immediate right of Stone $2$.
$1, 1, 1$ Stone $2$ is painted in color $1$.
$4$ $1, 1, 1, 2$ Stone $4$ is put on the immediate right of Stone $3$.
$5$ $1, 1, 1, 2, 3$ Stone $5$ is put on the immediate right of Stone $4$.
$6$ $1, 1, 1, 2, 3, 2$ Stone $6$ is put on the immediate right of Stone $5$.
$1, 1, 1, 2, 2, 2$ Stone $5$ is painted in color $2$.

Finally, the colors of Stones $1, 2, 3, 4, 5, 6$ will be $1, 1, 1, 2, 2, 2$, respectively.

This sample input satisfies the constraints of Subtasks 1, 3.

## 예제 입력 2

10
1
1
2
2
1
2
2
1
1
2


## 예제 출력 2

1
1
1
1
1
1
1
1
1
2


This sample input satisfies the constraints of all the subtasks.

## 채점 및 기타 정보

• 예제는 채점하지 않는다.