RT，WA10pts，只有#9过了，其他的全部都是几百几千的时候出问题，不知道是为什么

#include<bits/stdc++.h>
using namespace std;
struct treap{
    static const int N=1e5+5;
    int val[N],rnk[N],ls[N],rs[N],siz[N],tot,root,tag[N],mn[N];
    void down(int u){
        if(tag[u]){
            if(ls[u]){
                swap(ls[ls[u]],rs[ls[u]]);
                tag[ls[u]]=!tag[ls[u]];
            }
            if(rs[u]){
                swap(ls[rs[u]],rs[rs[u]]);
                tag[rs[u]]=!tag[rs[u]];
            }
            tag[u]=0;
        }
    }
    pair<int,int>splits(int u,int key){
        if(u==0)
            return make_pair(0,0);
        down(u);
        if(key<=siz[ls[u]]){//理论上左边会拥有key个
            pair<int,int>o=splits(ls[u],key);
            ls[u]=o.second;
            siz[u]=siz[ls[u]]+siz[rs[u]]+1;
            mn[u]=min(mn[ls[u]],min(mn[rs[u]],val[u]));
            return make_pair(o.first,u);
        }else{
            pair<int,int>o=splits(rs[u],key-siz[ls[u]]-1);
            rs[u]=o.first;
            siz[u]=siz[ls[u]]+siz[rs[u]]+1;
            mn[u]=min(mn[ls[u]],min(mn[rs[u]],val[u]));
            return make_pair(u,o.second);
        }
    }
    int merge(int u,int v){
        if(u==0)
            return v;
        if(v==0)
            return u;
        if(rnk[u]>rnk[v]){
            down(u);
            rs[u]=merge(rs[u],v);
            siz[u]=siz[ls[u]]+siz[rs[u]]+1;
            mn[u]=min(mn[ls[u]],min(mn[rs[u]],val[u]));
            return u;
        }else {
            down(v);
            ls[v]=merge(u,ls[v]);
            siz[v]=siz[ls[v]]+siz[rs[v]]+1;
            mn[v]=min(mn[ls[v]],min(mn[rs[v]],val[v]));
            return v;
        }
    }
    int getMinSiz(){
        int res=1,u=root;
        while(1){
            down(u);
            if(ls[u]&&mn[ls[u]]==mn[u])
                u=ls[u];
            else if(rs[u]&&mn[rs[u]]==mn[u]){
                res+=siz[ls[u]]+1;
                u=rs[u];
            }else return res+siz[ls[u]];
        }
    }
    int Node(int key){
        val[++tot]=key;
        rnk[tot]=rand();
        siz[tot]=1;
        mn[tot]=key;
        return tot;
    }
}N;
int n,a[100005];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(19260817);
    N.mn[0]=1e9;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        N.root=N.merge(N.root,N.Node(a[i]));
    }
    // cout<<"Yes Comrade!";
    // cout.flush();
    for(int i=1;i<=n;i++){
        int s=N.getMinSiz();
        cout<<s+i-1<<' ';
        pair<int,int>o=N.splits(N.root,s);
        pair<int,int>p=N.splits(o.first,s-1);
        swap(N.ls[p.first],N.rs[p.first]);
        N.tag[p.first]=!N.tag[p.first];
        N.root=N.merge(p.first,o.second);
    }
}