2023-ho-t1_Stone_Arranging_2 (JOI JOI)
Time limit: 2 seconds | Memory limit: 1024 MB | Task type: batch
Algorithms: data structures, stack, tree map

# 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 \le i \le 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 \le i \le N$) will be performed as follows:

- 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.
- 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.

## Input

Read the following data from the standard input:

$N$
$A_1$
$A_2$
$\vdots$
$A_N$

## Output

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

## Constraints

- $1 \le N \le 200\,000$.
- $1 \le A_i \le 10^9$ ($1 \le i \le N$).
- Given values are all integers.

## Subtasks

1. (25 points) $N \le 2\,000$.
2. (35 points) $A_i \le 2$ ($1 \le i \le N$).
3. (40 points) No additional constraints.

## Sample Input and Output

| Sample Input 1 | Sample Output 1 |
|---|---|
| 6 | 1 |
| 1 | 1 |
| 2 | 1 |
| 1 | 2 |
| 2 | 2 |
| 3 | 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.

| Sample Input 2 | Sample Output 2 |
|---|---|
| 10 | 1 |
| 1 | 1 |
| 1 | 1 |
| 2 | 1 |
| 2 | 1 |
| 1 | 1 |
| 2 | 1 |
| 2 | 1 |
| 1 | 1 |
| 1 | 1 |
| 2 | 2 |

This sample input satisfies the constraints of all the subtasks.

Starter code:

Grader code:

Setup script:

Evaluation script: