【MX-S1-T1】壁垒

题目描述

给定一个长度为 $n$ 的仅包含正整数的数列 $a$,保证 $n$ 是偶数。你需要重排 $a$,满足对于 $a$ 的每个长度为偶数的前缀,出现的数字种类数是偶数,或断定这样的重排方式不存在。 如果有多种重排方式满足条件,输出任意一种即可。

输入输出格式

输入格式


第一行一个正整数 $n$,保证 $n$ 是偶数。 第二行一个 $n$ 个正整数,描述数列 $a$。

输出格式


无解时输出 $-1$,否则输出一行 $n$ 个整数,描述重排后的数列 $a$。 本题使用**自定义校验器**检验你的答案是否正确,如果有多种重排方式满足条件,输出任意一种即可。

输入输出样例

输入样例 #1

6
2 3 3 4 1 1

输出样例 #1

1 3 3 1 2 4

输入样例 #2

2
1 1

输出样例 #2

-1

说明

__【样例解释 1】__ $\{1,3\},\{1,3,3,1\},\{1,3,3,1,2,4\}$ 这些集合的数字种类数都是偶数。 __【数据范围】__ __本题使用子任务捆绑测试。__ 对于 $100\%$ 的数据,$2\le n\le 10^5$,$1\le a_i\le n$,保证 $n$ 是偶数。 | 子任务编号 | $n\le $ | $a_i\le $ | 分值 | | ---------- | ------- | --------- | ---- | | $1$ | $10$ | $n$ | $20$ | | $2$ | $20$ | $n$ | $20$ | | $3$ | $10^5$ | $2$ | $20$ | | $4$ | $10^5$ | $10$ | $20$ | | $5$ | $10^5$ | $n$ | $20$ |