#P5181. [Baltic2016]Swap

    ID: 4250 传统题 1000ms 512MiB 尝试: 23 已通过: 7 难度: 9 上传者: 标签>难度分类提高+/省选-贪心延迟决策堆贪心数据结构二叉堆排序与序列处理离散化CF2600

[Baltic2016]Swap

最小字典序序列

给定一个长度为n的序列Xn,该序列中没有重复的数字。

你有n-1次操作的机会:在每次操作机会时对应的有着k=2,3,4,...n,(在第1次交换机会时k=2,以此类推)

你可以交换X[k]和X⌊k/2⌋X_{\lfloor k/2\rfloor},也可以不进行操作。求在执行完操作后,最小字典序的序列。

输入输出格式

输入格式

从标准输入读入。第一行是序列长度 nn。

第二行:长度为n的数列

1≤n≤2×1051\le n\le2\times10^5。

输出格式

向标准输出写出长度为 nn 的答案序列。

样例

样例输入

5
3 4 2 5 1

样例输出

2 1 3 4 5