Robotic Sort

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long
#define keyTree (son[son[rt][1]][0])
static const int INF = 2000000000;
static const int M = 100005;
int obj[M],A[M];
struct node{
    int x,pos;
    bool operator <(const node &tmp)const{
        if(x!=tmp.x)return x<tmp.x;
        return pos<tmp.pos;
    }
}Q[M];
struct SplayTree{
    int fa[M],son[M][2];
    int val[M],sz[M],mi[M];
    bool lazy[M];
    int rt,tot;
    
    void clear(){
        rt=tot=0;
        memset(lazy,false,sizeof(lazy));
        memset(fa,0,sizeof(fa));
        memset(son,0,sizeof(son));
        memset(val,0,sizeof(val));
        memset(sz,0,sizeof(sz));
    }
    SplayTree(){
        clear();
    }
    void Newnode(int &u,int f,int x){
        u=++tot;
        fa[u]=f;
        mi[u]=val[u]=x;
        lazy[u]=false;
        sz[u]=1;
        son[u][0]=son[u][1]=0;
        if(!rt)rt=u;
    }
    void Up(int p){
        sz[p]=1;
        lazy[p]=false;
        mi[p]=val[p];
        if(son[p][0]){
            sz[p]+=sz[son[p][0]];
            mi[p]=min(mi[p],mi[son[p][0]]);
        }
        if(son[p][1]){
            sz[p]+=sz[son[p][1]];
            mi[p]=min(mi[p],mi[son[p][1]]);
        }
    }
    void Rev(int p){
        lazy[p]^=true;
        int t=son[p][0];
        son[p][0]=son[p][1];
        son[p][1]=t;
    }
    void Down(int p){
        if(lazy[p]){
            if(son[p][0])Rev(son[p][0]);
            if(son[p][1])Rev(son[p][1]);
            lazy[p]=false;
        }
    }
    void Rotate(int p){
        int F=fa[p];
        int d=son[F][1]==p;
        son[F][d]=son[p][!d];
        if(son[p][!d])fa[son[p][!d]]=F;
        fa[p]=fa[F];
        son[fa[p]][son[fa[p]][1]==F]=p;
        fa[F]=p;
        son[p][!d]=F;
        //
        Up(F);
    }
    void Splay(int p,int goal){
        while(fa[p]!=goal){
            int F=fa[p];
            if(fa[F]!=goal){
                if(son[F][1]==p^son[fa[p]][1]==F)Rotate(p);
                else Rotate(F);
            }
            Rotate(p);
        }
        Up(p);
        if(!goal)rt=p;
    }
    void RotateTo(int k,int goal){//(k+1)大
        int p=rt;
        Down(p);
        while(sz[son[p][0]]!=k){
            if(sz[son[p][0]]>k)p=son[p][0];
            else{
                k-=sz[son[p][0]]+1;
                p=son[p][1];
            }
            Down(p);
        }
        Splay(p,goal);
    }
    void Insert(int n){
        for(int i=1;i<=n;++i){
            scanf("%d",&A[i]);
            Q[i]=(node){A[i],i};
        }
        sort(Q+1,Q+1+n);
        for(int i=1;i<=n;++i){
            A[Q[i].pos]=i;
        }
        Newnode(rt,0,INF);
        Newnode(son[rt][1],rt,INF);
        build(keyTree,son[rt][1],1,n);
        Up(son[rt][1]);
        Up(rt);
    }
    void build(int &u,int f,int L,int R){
        int mid=L+R>>1;
        Newnode(u,f,A[mid]);
        obj[A[mid]]=u;
        if(L==R)return ;
        if(L!=mid)build(son[u][0],u,L,mid-1);
        build(son[u][1],u,mid+1,R);
        Up(u);
    }
    void Solve(int pos,int n){
        int L=pos;
        RotateTo(L-1,0);
        RotateTo(n+1,rt);
        int p=keyTree,R=0;
        Down(p);
        while(val[p]!=mi[p]){
            if(mi[p]==mi[son[p][0]]){
                p=son[p][0];
            }else{
                R+=sz[son[p][0]]+1;
                p=son[p][1];
            }
            Down(p);
        }
        R+=sz[son[p][0]];//易错点
        //
        R+=L;
        printf("%d",R);
        if(pos!=n)putchar(' ');
        RotateTo(R+1,rt);
        Rev(keyTree);
    }
    void debug(int p){
        printf("v: %d , sz: %d , lazy: %d , val: %d , mi: %d\n",p,sz[p],lazy[p],val[p],mi[p]);
        printf("%d %d\n",son[p][0],son[p][1]);
        if(son[p][0])debug(son[p][0]);
//		printf("%d ",val[p]);
        if(son[p][1])debug(son[p][1]);
    }
}Tree;
int main(){
    int n;
    while(~scanf("%d",&n),n){
        Tree.clear();
        Tree.Insert(n);
        for(int i=1;i<=n;++i)Tree.Solve(i,n);
        puts("");
    }
    return 0;
}