题意：给一个数列，用某一特定的方法对其进行排序。其排序方法是，第i次排序时，找到第i小的元素的位置p，输出这个p，并将[i,p]这段区间翻转。进行n次这样的操作后，序列有序。

解题思路：以前用splay写过，思路是抄的别人的。学习treap后，重新再想了一下这个题，想到了一种新的思路。大概是这样的：首先，离散化还是有必要的，因为它会根据原序列里的位置定下其元素的大小。然后对于每次这样的操作，我们要找的必然是最小的那个元素。所以，我们要只需要维护区间的最小值，以及一个翻转标记。那么，我们如何寻找答案呢？显然，我们只要走最小值的值为i的那颗子树就好了，而且必然是能找到的。这样还有一个优点是，我们不需要像以前那种做法那样，从事先记录好的id往上走一遍了，因为我们往下走的时候，会把翻转标记都往下更新，这样，每次我们到达的节点，其信息必然是正确的，而且其子树的最小值信息也是正确的，那么我们就能根据这个最小值信息寻找相应的子树了。

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <math.h>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <time.h>
#define lowbit(x) (x&(-x))
#define ll __int64
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
#define new_edge(a,b,c) edge[tot].t = b , edge[tot].v = c , edge[tot].next = head[a] , head[a] = tot ++
using namespace std;

const int maxn = 211111 ;

int num[maxn] , pos[maxn] ;
int cmp ( int i , int j ) {
    if ( num[i] == num[j] ) return i < j ;
    return num[i] < num[j] ;
}

struct Treap {
    int c[2][maxn] , size[maxn] , p[maxn] ;
    int val[maxn] , mi[maxn] ;
    int col[maxn] ;
    int tot ;

    int new_node ( int v ) {
        size[++tot] = 1 ;
        p[tot] = rand () ;
        c[0][tot] = c[1][tot] = col[tot] = 0 ;
        mi[tot] = val[tot] = v ;
        return tot ;
    }

    int build ( int l , int  r ) {
        if ( l > r ) return 0 ;
        int mid = l + r >> 1 ;
        int temp = new_node ( num[mid] ) ;
        c[0][temp] = build ( l , mid - 1 ) ;
        c[1][temp] = build ( mid + 1 , r ) ;
        push_up ( temp ) ;
        return temp ;
    }

    void color ( int rt ) {
        if ( !rt ) return ;
        col[rt] ^= 1 ;
        swap ( c[0][rt] , c[1][rt] ) ;
    }

    void push_down ( int rt ) {
        if ( col[rt] ) {
            color ( c[0][rt] ) ;
            color ( c[1][rt] ) ;
            col[rt] = 0 ;
        }
    }

    void push_up ( int rt ) {
        int ls = c[0][rt] , rs = c[1][rt] ;
        size[rt] = size[ls] + size[rs] + 1 ;
        mi[rt] = min ( val[rt] , min ( mi[ls] , mi[rs] ) ) ;
    }

    int merge ( int x , int y ) {
        if ( !x ) return y ;
        if ( !y ) return x ;
        push_down  ( x ) ; push_down ( y ) ;
        if ( p[x] < p[y] ) {
            c[1][x] = merge ( c[1][x] , y ) ;
            push_up ( x ) ;
            return x ;
        }
        c[0][y] = merge ( x , c[0][y] ) ;
        push_up ( y ) ;
        return y ;
    }

    void split ( int rt , int &x , int &y , int k ) {
        push_down ( rt ) ;
        int ls = c[0][rt] , rs = c[1][rt] ;
        if ( val[rt] == k ) {
            x = rt , y = c[1][rt] ;
            c[1][rt] = 0 ;
            push_up ( rt ) ;
            return ;
        }
        if ( mi[ls] == k ) {
            split ( ls , x , y , k ) ;
            c[0][rt] = y ; y = rt ;
            push_up ( rt ) ;
            return ;
        }
        split ( rs , x , y , k ) ;
        c[1][rt] = x ; x = rt ;
        push_up ( rt ) ;
    }

    void cut ( int rt , int fa ) {
        push_down ( rt ) ;
        if ( !c[1][rt] ) {
            c[1][fa] = c[0][rt] ;
            return ;
        }
        cut ( c[1][rt] , rt ) ;
        push_up ( rt ) ;
    }

    int find ( int rt , int k ) {
        int x , y , temp ;
        split ( rt , x , y , k ) ;
        printf ( "%d " , size[x] + k - 1 ) ;
        push_down ( x ) ;
        if ( size[x] == 1 ) return y ;
        if ( !c[1][x] ) {
            color ( c[0][x] ) ;
            return merge ( c[0][x] , y ) ;
        }
        cut ( x , x ) ;
        color ( x ) ;
        return merge ( x , y ) ;
    }

    void init () {
        tot = 0 ;
        mi[0] = 11111111 ;
    }

} tree ;

int main() {
    srand ( time ( NULL ) ) ;
    int n , i ;
    while ( scanf ( "%d" , &n ) == 1 && n ) {
        tree.init () ;
        for ( i = 1 ; i <= n ; i ++ )
            scanf ( "%d" , &num[i] ) , pos[i] = i ;
        sort ( pos + 1 , pos + n + 1 , cmp ) ;
        for ( i = 1 ; i <= n ; i ++ ) num[pos[i]] = i ;
        int rt = 0 ;
        rt = tree.build ( 1 , n ) ;
        for ( i = 1 ; i < n ; i ++ ) rt = tree.find ( rt , i ) ;
        printf ( "%d\n" , n ) ;
    }
    return 0;
}

/*
20
8089 6286 8880 16892 5363 2990 4621 21227 6476 23659 31933 6505 23146 25222 30796 15967 24804 14923 19874 19874

20
7 4 8 11 3 1 2 14 5 16 20 6 15 18 19 10 17 9 13 12

6 7 7 6 9 12 11 9 18 11 18 19 20 16 17 16 20 19 19 20
6 7 7 6 9 12 11 9 18 11 18 20 13 18 15 20 18 20 19 20
*/