::::info[题意] 题意：给定一个长度为 $n$ 的排列 $a_{1 \dots n}$，你需要依次进行 $n-1$ 次操作，编号为 $2 \sim n$，在编号为 $k$ 的操作中你可以选择交换 $a_{k},a_{\lfloor \frac{k}{2} \rfloor}$ 也可以什么都不干。求最后可能得到的字典序最小的排列。

$n \le 2 \times 10^5$。 ::::

$k$ 和 $\lfloor \frac{k}{2} \rfloor$ 同时出现，很难不让我们联想到一些常见的结构。是的没错，完全二叉树。于是我们反手建一颗 $n$ 个点的完全二叉树。这样，编号为 $k$ 的操作等价于交换 $k$ 与 $k$ 的父亲的权值，而最后的 $a$ 相当于二叉树的 $\mathrm{BFS}$ 序列。

根据字典序的性质，我们肯定希望每个点的父节点的权值大小越小越好。同时我们发现，对于每一个子树，只要这个子树内点的权值的集合被确定了，整个子树内的排列方式就是确定且独立的。因此，我们考虑遍历整颗树。假设现在遍历到节点 $u$，设其左孩子为 $l$，右孩子为 $r$，我们考虑 $l,r$ 该如何交换才能使 $a_u$ 最小。记 $M=\min(a_u,a_l,a_r)$。

• 当 $M=a_u$，这个时候 $a_l,a_r$ 绝对不能和 $a_u$ 交换，因为交换一定会让结果更劣。此时，我们直接递归 $l,r$ 即可。
• 当 $M=a_l$，我们只能在操作编号为 $l$ 的时候一发操作让 $a_u,a_l$ 交换，后面我们就不动 $a_r$ 了。交换后直接递归 $l,r$ 即可。
• 当 $M=a_r$，这是最麻烦的情况。我们既可以先交换 $a_l,a_u$ 再交换 $a_r,a_u$，也可以不交换 $a_l,a_u$ 并交换 $a_r,a_u$。

我们发现，上面的分类讨论中我们的不确定的点主要在第三类情况中。现在，我们对这一类情况进行进一步的讨论。

我们假设此时 $a_l=x,a_u=y$。现在，我们有两种不同的可能的情况：

• 操作后，$a_u=M,a_l=x,a_r=y$。
• 操作后，$a_u=M,a_l=y,a_r=x$。

注意到两种情况具有一定的对称性，因此我们先不妨设 $x < y$。根据字典序的性质，我们肯定想要把 $x$ 放在更前面的位置。所以我们直接爆搜，搜索两种情况：把 $x$ 放在 $l$ 所在子树中位置更好还是放在 $r$ 所在子树中位置更好。对于递归的情况，我们继续按照上面讨论的方法来做即可。更具体地，我们假设 $f(u,v)$ 为对于以 $u$ 为根的子树，当 $a_u=v$ 时我们最优能把 $v$ 放到的位置。那么我们只需要比较 $f(l,x)$ 和 $f(r,x)$ 即可。注意，我们在整个过程中要对 $f$ 记忆化。

你可能会问这个做法看起来好 $\mathcal{O}\left(n^2\right)$ 啊！但实际上考虑到树高只有 $\mathcal{O}\left(\log n\right)$ 并且我们有记忆化，实际上有用的状态的数量级大致是 $\mathcal{O}\left(n \log n\right)$ 的。因此，如果你 $f$ 和我一样用 unordered_map 的话最终复杂度就是 $\mathcal{O}\left(n \log n\right)$。

::::success[一份 C++ 实现]

#include <bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
#define INF 0x3f3f3f3f
using namespace std;
const int N=1e6+10;
int n,a[N];
unordered_map<int,unordered_map<int,int>>mp;
int getpos(int u,int val,int fa){
    if(u>n) return fa;
    if(mp[u][val]) return mp[u][val];
    int ls=(u<<1);int rs=(u<<1|1);
    if(val<a[ls]&&val<a[rs]){
        return mp[u][val]=u;
    }
    else if(a[ls]<val&&a[ls]<a[rs]){
        return mp[u][val]=getpos(ls,val,u);
    }
    else{
        if(a[ls]<val){
            if(getpos(ls,a[ls],u)>getpos(rs,a[ls],u)){
                return mp[u][val]=getpos(ls,val,u);
            }
            else return mp[u][val]=getpos(rs,val,u);
        }
        else return mp[u][val]=min(getpos(ls,val,u),getpos(rs,val,u));
    }
}
void dfs(int u){
    if(u>n) return;
    int ls=(u<<1);
    int rs=(u<<1|1);
    if(a[u]<a[ls]&&a[u]<a[rs]){
        dfs(ls);dfs(rs);return;
    }
    else if(a[ls]<a[u]&&a[ls]<a[rs]){
        swap(a[u],a[ls]);
        dfs(ls);dfs(rs);return;
    }
    else{
        swap(a[u],a[rs]);
        if(a[ls]>a[rs]) swap(a[ls],a[rs]);
        int x=a[ls];
        if(getpos(ls,x,ls)>getpos(rs,x,rs)) swap(a[ls],a[rs]);
        dfs(ls);dfs(rs);return;
    }
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=n+1;i<=2*n+1;i++) a[i]=INF;
    dfs(1);
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
    cout<<'\n';
    return 0;
}

::::