分数: 500 点
问题陈述
有一个空数组 A。对于 i = 1,2,\ldots,N,依次执行以下操作:
- 插入号码 i 进入 A 使其成为 P_i- 从开头算起的第一个元素。
- 更准确地说,替换 A 与第一个的串联 P_i-1 的元素 A,那么 i,则剩余元素 A 从 P_i- 第一个元素,按此顺序。
输出最终数组 A 所有操作完成后。
约束
- 1 \leq N \leq 5\times 10^5
- 1 \leq P_i \leq i
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N P_1 P_2 \ldots P_N
输出
令最终数组为 A = (A_1, A_2, \ldots, A_N)。 打印 A_1, A_2, \ldots, A_N 按此顺序,用空格分隔。
示例输入 1
4 1 1 2 1
示例输出 1
4 2 3 1
操作执行如下:
- 插入号码 1 使其成为第一个元素 A。现在, A = (1).
- 插入号码 2 使其成为第一个元素 A。现在, A = (2, 1).
- 插入号码 3 使其成为第二个元素 A。现在, A = (2, 3, 1).
- 插入号码 4 使其成为第一个元素 A。现在, A = (4, 2, 3, 1).
示例输入 2
5 1 2 3 4 5
示例输出 2
1 2 3 4 5