AT_abc337_c [ABC337C] Lining Up 2

题目描述

有 $N$ 个人（编号为 $1, 2, \ldots, N$）排成一列。

排列的信息以长度为 $N$ 的数列 $A=(A_1, A_2, \ldots, A_N)$ 给出。

$A_i\ (1\leq i\leq N)$ 表示如下信息：

• 当 $A_i = -1$ 时，第 $i$ 个人站在队列的最前面。
• 当 $A_i \neq -1$ 时，第 $i$ 个人站在第 $A_i$ 个人的正后方。

请输出队列中从前到后的人的编号。

输入格式

输入以如下格式从标准输入给出。

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

若队列中从前到后依次为 $s_1, s_2, \ldots, s_N$ 号人，请按顺序用空格分隔输出 $s_1, s_2, \ldots, s_N$。

输入输出样例 #1

输入 #1

6
4 1 -1 5 3 2

输出 #1

3 5 4 1 2 6

输入输出样例 #2

输入 #2

10
-1 1 2 3 4 5 6 7 8 9

输出 #2

1 2 3 4 5 6 7 8 9 10

输入输出样例 #3

输入 #3

30
3 25 20 6 18 12 26 1 29 -1 21 17 23 9 8 30 10 15 22 27 4 13 5 11 16 24 28 2 19 7

输出 #3

10 17 12 6 4 21 11 24 26 7 30 16 25 2 28 27 20 3 1 8 15 18 5 23 13 22 19 29 9 14

说明/提示

限制条件

• $1 \leq N \leq 3 \times 10^5$
• $A_i = -1$ 或 $1 \leq A_i \leq N\ (1 \leq i \leq N)$
• 存在且仅存在一种与给定信息不矛盾的排列方式
• 所有输入均为整数

样例解释 1

从前到后，依次为第 $3$、第 $5$、第 $4$、第 $1$、第 $2$、第 $6$ 个人时，与给定信息一致。实际上：

• 第 $1$ 个人站在第 $4$ 个人的正后方。
• 第 $2$ 个人站在第 $1$ 个人的正后方。
• 第 $3$ 个人站在队列最前面。
• 第 $4$ 个人站在第 $5$ 个人的正后方。
• 第 $5$ 个人站在第 $3$ 个人的正后方。
• 第 $6$ 个人站在第 $2$ 个人的正后方。

可以确认与给定信息一致。因此，请按顺序输出 $3, 5, 4, 1, 2, 6$，用空格分隔。

由 ChatGPT 4.1 翻译