Description

JOI 君有 $N$ 颗围棋子。这些棋子从 $1$ 到 $N$ 编号。每颗棋子的颜色是一个介于 $1$ 和 $10^9$ 之间的整数（包含 $1$ 和 $10^9$）。一开始，第 $i$ 颗棋子（$1 \le i \le N$）的颜色是 $A_i$。

接下来，JOI 君将进行 $N$ 次操作。他会将棋子排成一行放在桌子上。第 $i$ 次操作（$1 \le i \le N$）将按如下方式进行：

1. JOI 君将第 $i$ 颗棋子放在第 $i-1$ 颗棋子的右边。但是，当 $i = 1$ 时，JOI 君会将第 1 颗棋子放在桌子上。
2. 如果在第 $1, 2, \cdots, i-1$ 颗棋子中有一颗棋子的当前颜色与第 $i$ 颗棋子的颜色相同，设 $j$ 为此类棋子的最大索引，JOI 君将用颜色 $A_i$ 涂色第 $j+1, j+2, \cdots, i-1$ 颗棋子。

为了确认操作是否正确执行，JOI 君想提前知道所有操作执行后棋子的颜色。

给定围棋子的相关信息，编写一个程序来确定 $N$ 次操作后棋子的颜色。

Input Format

从标准输入读取以下数据。

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

Output Format

向标准输出写入 $N$ 行。第 $i$ 行（$1 \le i \le N$）应包含第 $i$ 颗棋子在 $N$ 次操作后颜色。

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

Hint

样例

样例 1

操作按下表执行。

最终，第 1, 2, 3, 4, 5, 6 颗棋子的颜色分别为 1, 1, 1, 2, 2, 2。

此样例输入满足子任务 1, 3 的约束。

样例 2

此样例输入满足所有子任务的约束。

约束

• $1 \le N \le 2 \times 10^5$。
• $1 \le A_i \le 10^9$ ($1 \le i \le N$)。
• 给定的值都是整数。

子任务

1. (25 分) $N \le 2 000$。
2. (35 分) $A_i \le 2$ ($1 \le i \le N$)。
3. (40 分) 无额外约束。

题面翻译由 ChatGPT-4o 提供。