题目描述

莫图努伊岛上的居民信奉女神特菲提，她特别喜爱中位数和整数。

为了纪念她，人们发明了一个游戏：

• 选择 $n$ 个互不相同的整数，第 $i$ 个数为 $a_i$。
• 创建一个空的数字集合 $m$。
• 按照任意顺序逐个将数字添加到 $m$ 中，使得在每一步添加完当前数字后，集合 $m$ 元素的中位数始终保持为整数。

在此问题中，中位数定义如下：将集合 $m$ 的元素按升序排列。如果集合大小为奇数，则中位数等于所得序列的中间元素；如果为偶数，则中位数等于两个中间元素的平均值。

莫阿娜在出发冒险前给希米亚留下了 $n$ 个互不相同的整数。请帮助希米亚在莫阿娜回来之前完整地填满集合 $m$。

输入格式

第一行包含一个整数 $n$——数字的数量（$1 \le n \le 10^5$）。

第二行列出 $n$ 个不同的整数 $a_i$——为游戏选择的数字（$1 \le a_i \le 10^9$）。

输出格式

按照将数字添加到集合中的顺序输出数组 $a$ 中的数字，使得集合的中位数始终保持为整数。

如果无法将所有数字添加到 $m$ 中，则输出单个数字 $-1$。

5
1 2 3 4 5

4 2 5 1 3

2
2 9

-1