logo AlgoBeat OnlineJudge
登录 注册

#214672. [IO 2024 #3] 整数中位数

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

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

为了纪念她,人们发明了一个游戏:

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

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

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

输入格式

第一行包含一个整数 ——数字的数量()。

第二行列出 个不同的整数 ——为游戏选择的数字()。

输出格式

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

如果无法将所有数字添加到 中,则输出单个数字

样例

样例输入 1

5
1 2 3 4 5

样例输出 1

4 2 5 1 3

样例输入 2

2
2 9

样例输出 2

-1