AT_joi2023ho_a 碁石ならべ 2 (Stone Arranging 2)

JOI 君有 $N$ 个围棋子。每个棋子都被编号为 $1$ 到 $N$，且被涂上了用 $1$ 到 $10^9$ 之间的整数表示的颜色。最初，第 $i$ ($1 \leq i \leq N$) 个棋子的颜色为 $A_i$。 JOI 君接下来要进行 $N$ 次操作，把围棋子按一行依次放在桌子上。第 $i$ 次操作（$1 \leq i \leq N$）按照如下步骤进行： 1. 将第 $i$ 个棋子放在第 $i-1$ 个棋子的右侧。如果 $i = 1$，则将第 $1$ 个棋子放在桌子上。 2. 在第 $1, 2, \dots, i-1$ 个棋子中，如果存在当前颜色与第 $i$ 个棋子相同的棋子，则取编号最大的那一个记为 $j$，将第 $j+1, j+2, \dots, i-1$ 个棋子的颜色全部改为 $A_i$。 为了检验是否正确操作，JOI 君想提前了解所有操作后每个棋子的颜色。 给定棋子的信息，请编写程序，求出经过 $N$ 次操作后每个棋子的颜色。

输入将以下述格式由标准输入给出： > $N$ > $A_1$ > $A_2$ > $\vdots$ > $A_N$

请按顺序输出 $N$ 行。第 $i$ 行（$1 \leq i \leq N$）输出经过 $N$ 次操作后第 $i$ 个棋子的颜色。

## 子任务 1. （$25$ 分）$N \leq 2\,000$。 2. （$35$ 分）$A_i \leq 2$（$1 \leq i \leq N$）。 3. （$40$ 分）没有额外限制。 --- ### 样例解释 1 操作过程如下表： | 操作 | 棋子颜色排列 | 说明 | | :--- | :----------- | :--- | | $1$ | $1$ | 第 $1$ 个棋子放上桌。| | $2$ | $1,2$ | 第 $2$ 个棋子放在第 $1$ 个棋子右边。| | $3$ | $1,2,1$ | 第 $3$ 个棋子放在第 $2$ 个棋子右边。| | $3$ | $1,1,1$ | 将第 $2$ 个棋子的颜色改为 $1$。| | $4$ | $1,1,1,2$ | 第 $4$ 个棋子放在第 $3$ 个棋子右边。| | $5$ | $1,1,1,2,3$ | 第 $5$ 个棋子放在第 $4$ 个棋子右边。| | $6$ | $1,1,1,2,3,2$ | 第 $6$ 个棋子放在第 $5$ 个棋子右边。| | $6$ | $1,1,1,2,2,2$ | 将第 $5$ 个棋子的颜色改为 $2$。| 最终，第 $1,2,3,4,5,6$ 个棋子的颜色依次为 $1,1,1,2,2,2$。 本输入样例满足子任务 $1, 3$ 的限制条件。 --- ### 样例解释 2 本输入输出样例满足所有子任务的限制条件。 # 数据范围 - $1 \leq N \leq 200\,000$。 - $1 \leq A_i \leq 10^9$（$1 \leq i \leq N$）。 - 所有输入均为整数。 由 ChatGPT 5 翻译