P12702 [KOI 2022 Round 2] 食事计划

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

在 KOI 国家，铁柱所在的地方有 $N$ 个餐厅。每个餐厅只售卖一种食物，食物的类型通过整数 $A_i$ 来表示，$i$（$1 \leq i \leq N$）。 铁柱计划访问所有的餐厅，并为自己制定一个食事计划。铁柱的食事计划可以用从 $1$ 到 $N$ 的整数排列 $P$ 来表示。举例来说，如果 $P = [2, 4, 3, 1]$，这意味着铁柱将依次访问餐厅 2、4、3 和 1。 由于铁柱不希望连续吃相同类型的食物，所以在他的食事计划中，连续的两个餐厅必须提供不同类型的食物。也就是说，对于 $i = 1, 2, \dots, N-1$，$A_{P_i} \neq A_{P_{i+1}}$ 必须成立，而符合这一条件的食事计划被称为合法食事计划。 例如，假设 $N = 9$，且提供的食物类型是 $A = [1, 1, 1, 2, 2, 3, 3, 4, 3]$，则如果铁柱的食事计划是 $P = [3, 4, 1, 5, 6, 2, 7, 8, 9]$，那么计划中的每两个相邻餐厅的食物类型都不同，符合条件。 若铁柱的食事计划是 $P = [1, 4, 2, 5, 6, 3, 7, 8, 9]$，这也是一个合法的食事计划，并且是按字典顺序最前的合法计划。 然而，若食物类型是 $A = [1, 1, 1]$，无论怎样安排食事计划，都无法满足“连续两餐不同类型”的要求。 当给定 $N$ 个餐厅的食物类型时，如果无法制定合法的食事计划，则输出 `-1`；否则，输出字典序最前的合法食事计划。

第一行给出整数 $N$，表示餐厅的数量。 第二行给出 $N$ 个整数 $A_1, A_2, \dots, A_N$，表示每个餐厅的食物类型。

如果无法制定合法的食事计划，输出 `-1`。如果能够制定合法的食事计划，则输出字典序最前的合法食事计划 $P$，每个数之间用一个空格分隔。

**约束条件** - $1 \leq N \leq 300\,000$ - $1 \leq A_i \leq N$ **子任务** 1. （5 分）$N \leq 8$ 2. （12 分）$N \leq 20$ 3. （32 分）$N \leq 5\,000$ 4. （51 分）无额外约束条件