#4337. 排队2(Lining Up 2)

排队2(Lining Up 2)

题目描述

NN个人站成一排:第11个人、第22个人、...、第NN个人。
你被给定了一个长度为N的序列A=(A1,A2,...,AN)A=(A_1,A_2,...,A_N)来描述人们的排列方式。
Ai(1iN)A_i (1 ≤ i ≤ N) 表示以下信息:

  • 如果 Ai=1A_i = -1,第ii个人站在队伍的最前面;
  • 如果 Ai1A_i ≠ -1,第ii个人站在第AiA_i个人的正后方。

请按照从前到后的顺序输出队伍中人们的编号。

输入格式

输入将从标准输入中以下列格式给出:
NN
A1A_1 A2A_2 \cdots ANA_N

输出格式

如果第s1s_1个人、第s2s_2个人、...、第sNs_N个人按此顺序从前到后站在队伍中,请按此顺序输出s1,s2,s_1, s_2, \cdotssNs_N,用空格分隔。

样例

6
4 1 -1 5 3 2
3 5 4 1 2 6
10
-1 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10
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
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解释

如果第3个人、第5个人、第4个人、第1个人、第2个人和第6个人按此顺序从前到后站在队伍中,那么这种排列与给定的信息相符。
确实,可以看到:

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

因此,按顺序输出3、5、4、1、2和6,用空格分隔。

数据范围

1N3×1051 ≤ N ≤ 3 × 10^5
Ai=11AiN(1iN)A_i = -1 或 1 ≤ A_i ≤ N (1 ≤ i ≤ N)
存在唯一一种与给定信息一致的NN个人的排列方式
所有输入值都是整数。

来源

  • AtCoder ABC337C