K. 别墅区 - 2019级新生编程能力测试

仪表盘

单点时限: 1.0 sec

内存限制: 256 MB

Cuber QQ 拥有一个别墅区。别墅区的结构是一棵完全二叉树（根结点是 Cuber QQ 的住宅，下面就依次是 xjj 的住宅），就像下面这棵树一样。

上图的这棵完全二叉树有一个特点，就是所有父结点的权值都比子结点的权值要小（注意：圆圈里面的数是权值，圆圈上面的数是这个结点的编号）。符合这样特点的完全二叉树我们称为小根堆。

小根堆的根的权值最小，且根的两个子树也是一个小根堆。可以用一个数组 $a$ 来记录一棵完全二叉树， $a_{1}$ 为根结点，若结点 $a_{i}$ 不是根结点，那么它的父亲为 $a_{⌊ \frac{i}{2} ⌋}$ ；若结点 $a_{j}$ 不是叶子结点，那么它的左儿子为 $a_{2 j}$ ，它的右儿子为 $a_{2 j + 1}$ 。

现在给你一列 $n$ 个数，要你按一定顺序依次插入数组 $a$ 中（即第 $i$ 个数为 $a_{i}$ ），这个数组 $a$ 记录的完全二叉树最后得出来的就已经是一个小根堆，若有多种方法，输出字典序最大的一组。

输入格式

第1行为一个正整数 $n (n \leq 65535)$ ，表示数列的长度。

第2行包含 $n$ 个正整数，为这个数列的 $n$ 个数，数字之间用空格隔开。数字不超过 $10^{8}$ 且各不相同。

为了简化，数据保证 $n = 2^{k} - 1$ ，即保证最后的堆是一棵满二叉树。

输出格式

输出一行 $n$ 个数，依次输出描述小根堆的完全二叉树的数组 $a$ ，数字之间用空格隔开，行末换行并没有空格。

样例

Input

3
1 2 3

Output

1 3 2

NaN

A. 救救环球港 B. 二进制数 C. 俄罗斯方块 D. 可旋栈 E. 超越方程 F. 计算日期 G. 电子警察 H. 卡布列克常数 I. 分组 J. 数星星 K. 别墅区 L. DongDong学英语 M. 消消乐

比赛状态发生变化，点 OK 刷新。

OK

2019级新生编程能力测试

输入格式

输出格式

样例

题目列表

服务

开源

关于我们