题目内容

多多是电商平台的前端开发工程师，负责商品详情页的评价展示模块。评价区收到 $N$ 条评价，每条评价有一个星级评分（$1$ 到 $5$ 星）。多多希望将评价按一定顺序展示，使得任意两条评价相邻的星级不同，避免连续高分或低分影响用户判断。在所有合法的展示顺序中，请输出 字典序最小 的一种，或报告不可能。

给定 $N$ 条评价的星级 $r_1,r_2,\dots,r_N$ $(1 \le r_i \le 5)$。将它们重新排列为一行，使得相邻两个元素的值不同。 如果存在合法排列，输出字典序最小的一种；如果不存在，输出 $-1$。

两个排列 $a$ 和 $b$ 的字典序比较：从左到右找到第一个 $a_i \ne b_i$ 的位置，若 $a_i < b_i$ 则 $a$ 的字典序更小。

输入描述

第一行一个整数 $N$ $(1 \le N \le 10^5)$。

第二行 $N$ 个整数 $r_1,r_2,\dots,r_N$ $(1 \le r_i \le 5)$，表示每条评价的星级。

输出描述

如果不存在合法排列，输出 $-1$。

否则输出 $N$ 个整数，用空格分隔，表示字典序最小的一种合法排列顺序。

样例1

输入

5
1 1 1 2 3

输出

1 2 1 3 1

说明

样例1:$1$ 出现 $3$ 次，$\lceil 5/2 \rceil = 3$，恰好不超限。字典序最小的排列为 $(1,2,1,3,1)$。

样例2

输入

4
1 1 1 1

输出

-1

说明

样例2:$1$ 出现 $4$ 次，$\lceil 4/2 \rceil = 2$，超过上限，不可能。

样例3

输入

6
5 5 3 5 3 1

输出

1 5 3 5 3 5

说明

样例3:$5$ 出现 $3$ 次，$\lceil 6/2 \rceil = 3$，恰好不超限。字典序最小的排列为 $(1,5,3,5,3,5)$（首位取最小可用值 $1$，此后在保证剩余元素仍可合法排列的前提下逐位取最小）。