JOI-kun 有 $N$ 颗围棋子。棋子编号为 $1$ 到 $N$。每颗棋子的颜色是一个 $1$ 到 $10^9$ 之间的整数。最初，第 $i$ 颗棋子（$1 \le i \le N$）的颜色为 $A_i$。
现在，JOI-kun 将进行 $N$ 次操作。他会将棋子排成一行放在桌子上。第 $i$ 次操作（$1 \le i \le N$）执行如下：
- JOI-kun 将第 $i$ 颗棋子放在第 $i-1$ 颗棋子的右侧。但当 $i=1$ 时，JOI-kun 直接将第 $1$ 颗棋子放在桌子上。
- 如果在第 $1, 2, \dots, i-1$ 颗棋子中存在颜色与第 $i$ 颗棋子相同的棋子，设 $j$ 为满足此条件的棋子中编号最大的一个，JOI-kun 会将第 $j+1, j+2, \dots, i-1$ 颗棋子全部涂成颜色 $A_i$。
为了确认操作是否正确执行，JOI-kun 想提前知道所有操作完成后棋子的颜色。
给定棋子的信息，编写一个程序，确定 $N$ 次操作完成后每颗棋子的颜色。
输入格式
从标准输入读取以下数据：
$N$ $A_1$ $A_2$ $\vdots$ $A_N$
输出格式
向标准输出打印 $N$ 行。第 $i$ 行（$1 \le i \le N$）应包含 $N$ 次操作完成后第 $i$ 颗棋子的颜色。
数据范围
- $1 \le N \le 200\,000$
- $1 \le A_i \le 10^9$ ($1 \le i \le N$)
- 给定值均为整数。
子任务
- (25 分) $N \le 2\,000$
- (35 分) $A_i \le 2$ ($1 \le i \le N$)
- (40 分) 无附加限制。
样例
样例输入 1
6 1 2 1 2 3 2
样例输出 1
1 1 1 2 2 2
说明
操作执行过程如下表所示：
| 操作 | 桌上棋子的颜色 | 说明 |
|---|---|---|
| 1 | 1 | 将第 1 颗棋子放在桌上。 |
| 2 | 1, 2 | 将第 2 颗棋子放在第 1 颗棋子右侧。 |
| 3 | 1, 2, 1 | 将第 3 颗棋子放在第 2 颗棋子右侧。 |
| 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 颗棋子右侧。 |
| 1, 1, 1, 2, 2, 2 | 第 5 颗棋子被涂成颜色 2。 |
最终，第 1, 2, 3, 4, 5, 6 颗棋子的颜色分别为 1, 1, 1, 2, 2, 2。 该样例输入满足子任务 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
该样例输入满足所有子任务的限制。