配点: 100 点
問題文
打趣你 我有 N 围棋石头。每颗围棋棋子都有 它们的编号最大为 1 从 N 。1 以上 10^9 用以下整数表示的颜色进行绘制。一、围棋石 i (1 \leqq i \leqq N) 的颜色是 A_i 。
从现在开始JOI 执行 N 操作并将棋子放在桌子上。 1 我想将它们排列在一列中。i 回目 (1 \leqq i \leqq N)的操作执行如下。
- 碁石 i 围棋石 将其放在 i-1 的右侧。然而, 在i=1 的情况下,围棋棋子 将 1 放在桌子上。
- 碁石 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 \leqq i \leqq N)有 代表第N 操作后去石头 输出 i 的颜色。
制約
- 1 \leqq N \leqq 200\,000.
- 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N).
- 所有输入值都是整数。
小課題
- (25 点) N \leqq 2\,000.
- (35 点) A_i \leqq 2 (1 \leqq i \leqq 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
此输入/输出示例满足所有子任务约束。