← 返回题目列表

AtCoder · joi2023ho_a

A. 石头排列 2

中文机器翻译题面 查看原题

配点: 100 点

問題文

打趣你 我有 N 围棋石头。每颗围棋棋子都有 它们的编号最大为 1 从 N 。1 以上 10^9 用以下整数表示的颜色进行绘制。一、围棋石 i (1 \leqq i \leqq N) 的颜色是 A_i 。

从现在开始JOI 执行 N 操作并将棋子放在桌子上。 1 我想将它们排列在一列中。i 回目 (1 \leqq i \leqq 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 \leqq i \leqq N)有 代表第N 操作后去石头 输出 i 的颜色。


制約

  • 1 \leqq N \leqq 200\,000.
  • 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N).
  • 所有输入值都是整数。

小課題

  1. (25 点) N \leqq 2\,000.
  2. (35 点) A_i \leqq 2 (1 \leqq i \leqq N).
  3. (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

此输入/输出示例满足所有子任务约束。