题意： 给你n个数,每次先输出第i大的数的位置(如果有多个，选下标小的那个)，然后每次将第i个位置到第i大的数所在位置之间的数进行翻转。
思路：输入的数组可能有多个相同的值，我们可以进行两次排序把数组的值变为1---n(表示第几大)。
在建伸展树的时候我们可以顺便用pos[i]记录第i大的数的节点标号。
对于第i次操作，我们用col[]数组记录翻转标记，每次先把第i大的节点pos[i]旋转到根，那么它的位置为i+左儿子的个数。然后左儿子打上翻转标记，最后删除根。
注意：下放懒惰标记时只要交换左右儿子的节点标号就可以了，也正因为这个原因，
下放函数的位置记得要放在没有引用任何左右儿子信息之前， 这跟区间其它操作最大的区别。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define L ch[x][0]
#define R ch[x][1]
const int maxn = 100005;
int pos[maxn]; //pos[i]表示第i大的数的节点的标号
int n;
struct node {
int a, id;
bool operator <(const node &t) const {
return id < t.id;
}
}p[maxn];
bool cmp(const node &a, const node &b) {
return a.a < b.a || (a.a == b.a && a.id < b.id);
}
struct splayTree {
int sz[maxn], ch[maxn][2], pre[maxn];
bool col[maxn];
int root, tot;
void down(int x) {
if(col[x]) {
col[L] ^= 1;
col[R] ^= 1;
swap(L, R);
col[x] = 0;
}
}
void up(int x) {
sz[x] = sz[L] + sz[R] + 1;
}
void rotate(int &x, int f) {
int y = pre[x], z = pre[y];
down(y); down(x);
ch[y][!f] = ch[x][f];
pre[ch[x][f]] = y;
pre[x] = pre[y];
if(pre[x]) ch[z][ch[z][1] == y] = x;
ch[x][f] = y;
pre[y] = x;
up(y);
}
void splay(int &x, int g) {
while(pre[x] != g) {
int y = pre[x], z = pre[y];
down(z); down(y); down(x);
//不是区间翻转的题，这里的down可以不写，因为rotate里面有down， 但区间翻转要先down在去旋转，因为左右儿子会改变
if(z == g) rotate(x, ch[y][0] == x);
else {
int f = (ch[z][0] == y);
ch[y][!f] == x ? rotate(y, f) : rotate(x, !f);
rotate(x, f);
}
}
up(x);
if(!g) root = x;
}
int find(int k) {
int x = root;
while(sz[L]+1 != k) {
down(x);
if(sz[L]>= k) x = L;
else {
k -= sz[L]+1;
x = R;
}
}
return x;
}
void rto(int k, int g) {
int x = root;
while(1) {
down(x);
if(sz[L]+1 == k) break;
if(sz[L]>= k) x = L;
else {
k -= sz[L]+1;
x = R;
}
}
splay(x, g);
}
void newNode(int &x, int m, int fa) {
x = ++tot;
pos[p[m].a] = x;
pre[x] = fa;
sz[x] = 1;
L = R = 0;
col[x] = 0;
}
void build(int &x, int l, int r, int fa) {
if(l > r) return;
int m = (l + r) >> 1;
newNode(x, m, fa);
build(L, l, m-1, x);
build(R, m+1, r, x);
up(x);
}
void init(int n) {
tot = 0;
int i;
//数字可能相等，可以把数字预处理成1--n
for(i = 1; i <= n; i++) {
scanf("%d", &p[i].a);
p[i].id = i;
}
sort(p+1, p+n+1, cmp);
for(i = 1; i <= n; i++)
p[i].a = i;
sort(p+1, p+n+1);
build(root, 1, n, 0);
}
void print(int x) {
down(x);
printf("x: %d lson: %d rson: %d fa: %d lsz: %d rsz: %d\n", x, L, R, pre[x], sz[L], sz[R]);
if(L)print(L);
if(R)print(R);
}
void debug() {
printf("root = %d\n", root);
print(root);
}
void solve() {
for(int i = 1; i < n; i++) {
splay(pos[i], 0); //把值为i的节点旋到根
int x = root;
printf("%d ", sz[L]+i);
down(x); col[L] ^= 1; down(L); //根down，根的左儿子打翻转标记
if(sz[L]) { //有左儿子
rto(sz[L], root); //把左儿子的最右边的点旋到根
//删除根，根的左儿子代替根，新根的右儿子还是原根的右儿子，但父亲要修改
root = L;
ch[root][1] = R;
pre[root] = 0;
pre[R] = root;
}
else { //没有左儿子，直接把右儿子拉到根上来
root = ch[root][1];
pre[root] = 0;
}
up(root);
}
printf("%d\n", n);//最后只剩一个节点时一定是最后一个， 特判一下。
}
}spt;
int main() {
int i;
while( ~scanf("%d", &n) && n) {
spt.init(n);
spt.solve();
}
return 0;
}