分数: 800 点
问题陈述
Niwango 有 N 卡片,已编号 1,2,\ldots,N。 他现在将这些卡片排成一排。
Niwango想知道是否有一种方法可以在满足所有卡片的同时排列卡片 N 条件如下。 帮助他判断是否存在这样的方式。如果答案是肯定的,还要找到字典顺序最小的这种排列。
- 卡的右侧 1 (如果有)不是卡 a_1.
- 卡的右侧 2 (如果有)不是卡 a_2.
- \vdots
- 卡的右侧 N (如果有)不是卡 a_N.
约束
- 2 \leq N \leq 10^{5}
- 1 \leq a_i \leq N
- a_i \neq i
输入
输入由标准输入按以下格式给出:
N a_1 a_2 \ldots a_N
输出
如果没有安排满足条件,则打印 -1。如果存在这样的排列,则按以下格式打印字典顺序最小的此类排列:
b_1 b_2 \ldots b_N
在这里, b_i 代表 i左起第一张牌。
示例输入 1
4 2 3 4 1
示例输出 1
1 3 2 4
- 安排 (1,2,3,4) 按字典顺序小于 (1,3,2,4),但无效,因为它违反了“卡的直接右侧”的条件 1 不是卡 2."
示例输入 2
2 2 1
示例输出 2
-1
- 如果没有安排满足条件,则打印
-1.
示例输入 3
13 2 3 4 5 6 7 8 9 10 11 12 13 12
示例输出 3
1 3 2 4 6 5 7 9 8 10 12 11 13