1 #include<algorithm>
2 #include<cstdio>
3 #include<cassert>
4 using namespace std;
5 const int N = 100005;
6 int n,splsize;
7 struct node{
8 int flag,sz,ch[2],p;
9 } tree[N];
10 struct sample{
11 int id,v;
12 bool operator < (sample A)
const{
13 return A.v == v ? id < A.id : v < A.v;
14 }
15 }num[N];
16 // splay
17 inline
void upt(
int x){
18 tree[x].sz = tree[tree[x].ch[0]].sz + tree[tree[x].ch[1]].sz+1;
19 }
20 inline
void setchd(
int y,
int x,
int p){
21 tree[y].ch[p] = x; tree[x].p = y;
22 }
23 void rot(
int x){
24 int y = tree[x].p;
25 int chd = tree[y].ch[1] == x;
26 setchd(tree[y].p,x,tree[tree[y].p].ch[1] == y);
27 setchd(y,tree[x].ch[chd^1],chd);
28 setchd(x,y,chd^1);
29 upt(y); upt(x);
30 }
31 void pushup(
int x){
32 if(tree[x].flag) {
33 tree[x].flag=0;
34 swap(tree[x].ch[0],tree[x].ch[1]);
35 tree[tree[x].ch[0]].flag ^= 1;
36 tree[tree[x].ch[1]].flag ^= 1;
37 }
38 }
39 void dfs(
int x){
40 if(!x)
return ;
41 dfs(tree[x].p);
42 pushup(x);
43 }
44 void splay(
int x,
int rt){
45 dfs(x);
46 while(tree[x].p!=rt){
47 int y = tree[x].p;
48 int flag = tree[y].ch[1] == x;
49 if(tree[tree[x].p].p !=rt && flag == (tree[tree[y].p].ch[1] == y)) rot(y);
50 rot(x);
51 }
52 }
53 // function
54 void ins(
int x){
55 setchd(x-1,x,1);
56 tree[x].ch[0] = tree[x].ch[1] = tree[x].flag= 0;
57 splay(x,0);
58 }
59 int cal(
int x){
60 splay(x,0);
61 int ans = tree[tree[x].ch[0]].sz +1;
62 tree[tree[x].ch[0]].flag ^=1;
63 int u = tree[x].ch[0];
64 int v = tree[x].ch[1];
65 if(u==0) setchd(0,v,1);
66 else if(v==0) setchd(0,u,1);
67 else {
68 pushup(u); pushup(v);
69 while(tree[u].ch[1]){ u = tree[u].ch[1]; pushup(u);}
70 while(tree[v].ch[0]){ v = tree[v].ch[0]; pushup(v);}
71 splay(u,0); splay(v,u);
72 assert(tree[v].ch[0] == x);
73 tree[v].ch[0] = 0;
74 }
75 return ans;
76 }
77 // main
78 int main(){
79 tree[0].ch[0] = tree[0].ch[1] = tree[0].p = 0;
80 while(~scanf("%d",&n) && n){
81 for(
int i=0; i<n; i++){
82 scanf("%d",&num[i].v);
83 ins(i+1);
84 num[i].id = i;
85 }
86 sort(num,num+n);
87 for(
int i=0; i<n; i++){
88 int pos = num[i].id + 1;
89 int ans = cal(pos) + i;
90 if(i) printf(" ");
91 printf("%d",ans);
92 }
93 puts("");
94 }
95 }
96