Spoj Robotic Sort

#include <algorithm>
#include <cstdio>
#include <cstdlib>
using namespace std;


const int MAXN = 100000;


typedef struct item * tree;
struct item {
    tree l, r, p;
    int prior, cnt;
    bool rev;

    void init() {
        cnt = 1;
        rev = false;
        l = r = p = 0;
    }
};

inline int cnt (tree t) {
    return t ? t->cnt : 0;
}

inline void push (tree t) {
    if (!t)  return;
    if (t->l)  t->l->p = t;
    if (t->r)  t->r->p = t;
    if (t->rev) {
        t->rev = false;
        swap (t->l, t->r);
        if (t->l)  t->l->rev ^= true;
        if (t->r)  t->r->rev ^= true;
    }
}

inline void upd_cnt (tree t) {
    if (t) {
        t->cnt = cnt (t->l) + cnt (t->r) + 1;
        push (t);
    }
}

tree merge (tree l, tree r) {
    push (l),  push (r);
    if (!l || !r)
        return l ? l : r;
    if (l->prior > r->prior) {
        l->r = merge (l->r, r);
        upd_cnt (l);
        return l;
    }
    else {
        r->l = merge (l, r->l);
        upd_cnt (r);
        return r;
    }
}

void split (tree t, tree & l, tree & r, int key) {
    if (!t) {
        l = r = 0;
        return;
    }
    push (t);
    int cur_key = cnt (t->l) + 1;
    if (key < cur_key) {
        split (t->l, l, t->l, key);
        r = t;
    }
    else {
        split (t->r, t->r, r, key - cur_key);
        l = t;
    }
    upd_cnt (l),  upd_cnt (r);
    if (l)  l->p = 0;
    if (r)  r->p = 0;
}

void recpush (tree t) {
    if (t->p)  recpush (t->p);
    push (t);
}

int up (tree t) {
    recpush (t);
    int res = cnt (t->l);
    while (t->p) {
        if (t->p->r == t)
            res += cnt (t->p->l) + 1;
        t = t->p;
    }
    return res;
}


int n;
pair<int,int> a[MAXN];
int p[MAXN];
item ver[MAXN];
char buf[MAXN*10], *ptr;


inline int read_int() {
    while (*ptr == ' ')  ++ptr;
    int res = 0;
    while ('0' <= *ptr && *ptr <= '9')
        res = res * 10 + *ptr++ - '0';
    return res;
}

inline void print_int (int n) {
    char * beg = ptr;
    while (n) {
        *ptr++ = char ('0' + n % 10);
        n /= 10;
    }
    reverse (beg, ptr);
}


bool read() {
    gets (buf);
    ptr = buf;
    n = read_int();
    if (n == 0)
        return false;

    gets (buf);
    ptr = buf;
    for (int i=0; i<n; ++i)
        a[i] = make_pair (read_int(), i);
    return true;
}


void solve() {
    sort (a, a+n);
    for (int i=0; i<n; ++i) {
        p[a[i].second] = i;
        ver[i].init();
    }

    tree t = 0;
    for (int i=0; i<n; ++i)
        t = merge (t, &ver[p[i]]);

    ptr = buf;
    for (int i=0; i<n; ++i) {
        int key = up (&ver[i]);

        tree t1, t2, t3;
        split (t, t1, t2, key);
        split (t2, t2, t3, 1);
        if (t1)
            t1->rev ^= true;
        t = merge (t1, t3);

        if (i)
            *ptr++ = ' ';
        print_int (key + i + 1);
    }
    *ptr = 0;
    puts (buf);
}


int main() {

    for (int i=0; i<MAXN; ++i)
        ver[i].prior = rand();

    while (read())
        solve();

}