题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

在 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$，每个数之间用一个空格分隔。

9
1 1 1 2 2 3 3 4 3

1 4 2 5 6 3 7 8 9

3
1 1 1

-1

提示

约束条件

• $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 分）无额外约束条件