← 返回题目列表

AtCoder · dwacon6th_prelims_d

D. 安排

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

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