最近有人送给哥萨克一个包含 个整数的数组 。
胡子立刻想要对数组的元素进行排序，使得排序后数组中任意两个相邻的数字都不相同。在所有这样的排序中，他想找到字典序最小的那个。
回忆一下，字典序定义如下。假设有两个数组。找到第一个两个数组元素不同的位置。如果在该位置第一个数组的元素小于第二个数组的元素，则第一个数组字典序小于第二个数组；否则，第一个数组字典序大于第二个数组。例如，以下不等式成立：, , 。
第一行包含一个整数 —— 数组的元素个数。
第二行包含 个整数 —— 数组的元素。
如果无法对哥萨克的数组进行排序，则输出单个数字 。
否则，输出 个整数 —— 哥萨克的数组的字典序最小排序。
5 3 1 2 3 3
3 1 3 2 3
6 2 3 1 1 2 4
1 2 1 2 3 4
4 1 2 1 1
-1
在第一个样例中，存在唯一的排序。
在第二个样例中，还存在其他排序，例如： 或 。但所有这些排序在字典序上都大于 。
在第三个样例中，不存在有效的排序（数组中总会有两个 出现在相邻位置）。
本题采用 按测试点 评分。一些额外的限制条件：
翻译由 DeepSeek V3 完成
