输入共两行，第一行为一个整数N，N表示物品的个数，1<=N<=100000。第二行为N个用空格隔开的正整数，表示N个物品最初排列的编号。

输出共一行，N个用空格隔开的正整数P1,P2,P3…Pn，Pi表示第i次操作前第i小的物品所在的位置。 注意：如果第i次操作前，第i小的物品己经在正确的位置Pi上，我们将区间[Pi,Pi]反转(单个物品)。

6
3 4 5 1 6 2

4 6 4 5 6 6

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn=100010;

struct node

{

    int ch[2],fa,size,tag;

}p[maxn];

struct item

{

    int num,org;

}it[maxn];

int n,root,v[maxn];

bool cmp(item a,item b)

{

    if(a.num==b.num)    return a.org<b.org;

    return a.num<b.num;

}

int readin()

{

    int ret=0;    char gc;

    while(gc<'0'||gc>'9')    gc=getchar();

    while(gc>='0'&&gc<='9')    ret=ret*10+gc-'0',gc=getchar();

    return ret;

}

void pushup(int x)

{

    p[x].size=p[p[x].ch[0]].size+p[p[x].ch[1]].size+1;

}

void pushdown(int x)

{

    if(p[x].tag)

    {

        swap(p[x].ch[0],p[x].ch[1]);

        if(p[x].ch[0])    p[p[x].ch[0]].tag^=1;

        if(p[x].ch[1])    p[p[x].ch[1]].tag^=1;

        p[x].tag=0;

    }

}

void rotate(int x,int &k)

{

    int y=p[x].fa,z=p[y].fa,d=(x==p[y].ch[1]);

    if(y==k)    k=x;

    else    p[z].ch[y==p[z].ch[1]]=x;

    p[x].fa=z,p[y].fa=x,p[y].ch[d]=p[x].ch[d^1];

    if(p[x].ch[d^1])    p[p[x].ch[d^1]].fa=y;

    p[x].ch[d^1]=y;

    pushup(y),pushup(x);

}

void build(int l,int r,int last)

{

    if(l>r)    return ;

    int mid=l+r>>1;

    if(last)    p[v[last]].ch[mid>last]=v[mid];

    p[v[mid]].fa=v[last];

    build(l,mid-1,mid),build(mid+1,r,mid);

    pushup(v[mid]);

}

int find(int x,int y)

{

    pushdown(x);

    if(y==p[p[x].ch[0]].size+1)    return x;

    if(y<=p[p[x].ch[0]].size)    return find(p[x].ch[0],y);

    else    return find(p[x].ch[1],y-p[p[x].ch[0]].size-1);

}

int qrank(int x)

{

    if(x==root)    return p[p[x].ch[0]].size+1;

    int ret=qrank(p[x].fa);

    pushdown(x);

    if(x==p[p[x].fa].ch[0])    ret-=p[p[x].ch[1]].size+1;

    else    ret+=p[p[x].ch[0]].size+1;

    return ret;

}

void splay(int x,int &k)

{

    while(x!=k)

    {

        int y=p[x].fa,z=p[y].fa;

        if(y!=k)

        {

            if((x==p[y].ch[0])^(y==p[z].ch[0]))    rotate(x,k);

            else    rotate(y,k);

        }

        rotate(x,k);

    }

}

int main()

{

    scanf("%d",&n);

    int i;

    for(i=1;i<=n;i++)    it[i].num=readin(),it[i].org=i;

    sort(it+1,it+n+1,cmp);

    for(i=1;i<=n;i++)    v[it[i].org+1]=i;

    v[1]=n+1,v[n+2]=n+2;

    root=v[(n+3)>>1];

    build(1,n+2,0);

    for(i=1;i<n;i++)

    {

        int temp=qrank(i);

        printf("%d ",temp-1);

        splay(find(root,i),root);

        splay(find(root,temp+1),p[root].ch[1]);

        p[p[p[root].ch[1]].ch[0]].tag^=1;

    }

    printf("%d",n);

    return 0;

}