← 返回题目列表

AtCoder · abc392_f

I. 插入

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

分数: 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