题意：
将一列数字排序 排序规则是 每次找到最小值的位置loc 将1~loc全部数字颠倒 然后删掉第一位 直到排好序 排序要求是稳定的
思路：
这题要做的是 寻找区间最小值位置 翻转区间 的操作 因此能够想到用splay
仅仅须要每一个节点记录一个small 就能够实现找到最小值位置
翻转区间操作就是将splay的超级头转到最上面使之成为根 再把loc转到根以下 这时根的右儿子的左儿子就是须要翻转的区间 用一个rev延迟更新 然后将loc转到最上面是指成为根 删掉根 如此循环
注意：
因为翻转区间这样的更新会改变树的结构 因此不管是splay的时候还是做不论什么查找的时候都必须先把rev给down下去！。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
#define keytree ch[ch[root][1]][0]
#define L(x) ch[x][0]
#define R(x) ch[x][1]
#define N 100010
int n,tot,root;
int a[N],ch[N][2],pre[N],size[N],val[N],small[N],rev[N];
void newnode(int &u,int fa,int w)
{
u=++tot;
L(u)=R(u)=0;
pre[u]=fa;
size[u]=1;
small[u]=val[u]=w;
rev[u]=0;
}
void up(int u)
{
size[u]=size[L(u)]+size[R(u)]+1;
small[u]=min(val[u],min(small[L(u)],small[R(u)]));
}
void down(int u)
{
if(rev[u])
{
if(L(u)) rev[L(u)]^=1;
if(R(u)) rev[R(u)]^=1;
swap(L(u),R(u));
rev[u]=0;
}
}
void rotate(int u,int kind)
{
int fa=pre[u];
down(fa);
down(u);
ch[fa][!kind]=ch[u][kind];
pre[ch[u][kind]]=fa;
if(pre[fa]) ch[pre[fa]][ch[pre[fa]][1]==fa]=u;
pre[u]=pre[fa];
ch[u][kind]=fa;
pre[fa]=u;
up(fa);
}
void splay(int u,int goal)
{
int fa,kind;
down(u);
while(pre[u]!=goal)
{
if(pre[pre[u]]==goal)
{
down(pre[u]);
down(u);
rotate(u,L(pre[u])==u);
}
else
{
fa=pre[u];
down(pre[fa]);
down(fa);
down(u);
kind=L(pre[fa])==fa;
if(ch[fa][kind]==u)
{
rotate(u,!kind);
rotate(u,kind);
}
else
{
rotate(fa,kind);
rotate(u,kind);
}
}
}
up(u);
if(goal==0) root=u;
}
int getkth(int u,int k)
{
down(u);
int s=size[L(u)]+1;
if(s==k) return u;
if(s>k) return getkth(L(u),k);
else return getkth(R(u),k-s);
}
void build(int &u,int l,int r,int fa)
{
if(l>r) return ;
int mid=(l+r)>>1;
newnode(u,fa,a[mid]);
build(L(u),l,mid-1,u);
build(R(u),mid+1,r,u);
up(u);
}
void init()
{
root=tot=0;
L(root)=R(root)=pre[root]=size[root]=rev[root]=0;
val[root]=small[root]=N;
newnode(root,0,N);
newnode(R(root),root,N);
build(keytree,1,n,R(root));
up(R(root));
up(root);
}
int getmin(int u,int x)
{
down(u);
if(val[u]==x) return 1+size[L(u)];
if(small[L(u)]==x) return getmin(L(u),x);
if(small[R(u)]==x) return size[L(u)]+1+getmin(R(u),x);
}
int getpre(int u)
{
down(u);
u=L(u);
down(u);
while(R(u))
{
u=R(u);
down(u);
}
return u;
}
void remove()
{
if(L(root))
{
int i=getpre(root);
splay(i,root);
R(i)=R(root);
pre[R(root)]=i;
root=L(root);
pre[root]=0;
up(root);
}
else
{
root=R(root);
pre[root]=0;
}
}
struct input
{
int val,id;
bool operator<(const input fa) const
{
if(val==fa.val) return id<fa.id;
return val<fa.val;
}
}fzc[N];
int main()
{
int i,loc;
while(~scanf("%d",&n))
{
if(!n) break;
for(i=1;i<=n;i++)
{
scanf("%d",&fzc[i].val);
fzc[i].id=i;
}
sort(fzc+1,fzc+n+1);
for(i=1;i<=n;i++) a[fzc[i].id]=i;
init();
for(i=1;i<n;i++)
{
loc=getmin(root,i);
printf("%d ",loc+i-2);
splay(getkth(root,1),0);
splay(getkth(root,loc),root);
rev[keytree]^=1;
splay(getkth(root,loc),0);
remove();
}
printf("%d
",n);
}
return 0;
}