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 翻译