3359. 吉吉木与五彩方块

单点时限: 2.0 sec

内存限制: 256 MB

吉吉林有 $n$ 个方块,她把它们排成一列,这些方块五彩缤纷,非常好看。

但是有一件事情会让吉吉林非常难受,就是相邻的两个方块颜色一样。所以吉吉林想调整一下这些方块的顺序,使得不存在两个连续的颜色相同的方块。

这能做到吗?怎么做到?

输入格式

第一行一个整数 $n$ $(1 \leq n \leq 50~000)$。

第二行 $n$ 个整数,$a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq n)$,分别表示这 $n$ 个方块的颜色。

输出格式

输出 $a_1, a_2, \ldots, a_n$ 的一个排列 $b_1, b_2, \ldots, b_n$,使得 $\forall 1 \leq i \leq n -1, b_i \neq b_{i+1}$。

如果无解,输出 $-1$。

样例

Input
6
2 3 1 4 2 2
Output
2 1 2 3 2 4
Input
4
1 1 1 1
Output
-1

46 人解决,66 人已尝试。

56 份提交通过,共有 235 份提交。

4.6 EMB 奖励。

创建: 3 年前.

修改: 2 年,12 月前.

最后提交: 1 周,1 天前.

来源: 2017.9.27 ACM 选拔赛

题目标签