1 #include <cstdio>
2 #include <algorithm>
3 #include <cstring>
4
5 using namespace std;
6
7 #define Key_value (ch[ch[root][1] ][0])
8
9 const int maxn = 2e5+10;
10 const int INF = 0x3f3f3f3f;
11
12 int pre[maxn],ch[maxn][2],key[maxn],size[maxn];
13 int root,tot1;
14 int rev[maxn];
15 int s[maxn],tot2;
16 int N;
17
18 struct Node{
19 int num,id;
20 bool operator < (const Node &rhs) const
21 {
22 if(num == rhs.num) return id < rhs.id;
23 else return num < rhs.num;
24 }
25 }node[maxn];
26
27 void Treavel(int x)
28 {
29 if(x)
30 {
31 Treavel(ch[x][0]);
32 printf("结点:%2d: 左儿子 %2d 右儿子 %2d 父结点 %2d size= %2d val=%2d
",x,ch[x][0],ch[x][1],pre[x],size[x],key[x]);
33 Treavel(ch[x][1]);
34 }
35 }
36
37 void debug()
38 {
39 printf("root:%d
",root);
40 Treavel(root);
41 }
42
43 void NewNode(int &o,int father,int k)
44 {
45 o = k;
46 pre[o] = father;
47 ch[o][0] = ch[o][1] = 0;
48 rev[o] = 0;
49 size[o] = 1;
50 }
51 void update_rev(int o)
52 {
53 if(!o) return ;
54 swap(ch[o][0],ch[o][1]);
55 rev[o] ^= 1;
56 }
57 void push_up(int o)
58 {
59 int lson = ch[o][0],rson = ch[o][1];
60 size[o] = size[lson]+size[rson] + 1;
61 }
62 void push_down(int o)
63 {
64 if(rev[o])
65 {
66 update_rev(ch[o][0]);
67 update_rev(ch[o][1]);
68 rev[o] = 0;
69 }
70 }
71 void Build(int &x,int l,int r,int father)
72 {
73 if(l > r) return ;
74 int mid = (l+r)>>1;
75 NewNode(x,father,mid);
76 Build(ch[x][0],l,mid-1,x);
77 Build(ch[x][1],mid+1,r,x);
78 push_up(x);
79 }
80 void Init()
81 {
82 root = tot1 = tot2 = 0;
83 ch[root][0] = ch[root][1] = size[root] = pre[root] = 0;
84 rev[root] = 0;
85 NewNode(root,0,N+1);
86 NewNode(ch[root][1],root,N+2);
87
88 Build(Key_value,1,N,ch[root][1]);
89 push_up(ch[root][1]);
90 push_up(root);
91 }
92 void Rotate(int x,int kind)
93 {
94 int y = pre[x];
95 push_down(y);
96 push_down(x);
97 ch[y][!kind] = ch[x][kind];
98 pre[ch[x][kind] ] = y;
99 if(pre[y])
100 ch[pre[y] ][ch[pre[y]][1]==y ] = x;
101 pre[x] = pre[y];
102 ch[x][kind] = y;
103 pre[y] = x;
104 push_up(y);
105 }
106 void Splay(int x,int goal)
107 {
108 push_down(x);
109 while(pre[x] != goal)
110 {
111 if(pre[pre[x] ] == goal)
112 {
113 push_down(pre[x]);
114 push_down(x);
115 Rotate(x,ch[pre[x]][0]==x);
116 }
117 else
118 {
119 push_down(pre[pre[x] ]);
120 push_down(pre[x]);
121 push_down(x);
122 int y = pre[x];
123 int kind = ch[pre[y] ][0] == y;
124 if(ch[y][kind] == x)
125 {
126 Rotate(x,!kind);
127 Rotate(x,kind);
128 }
129 else
130 {
131 Rotate(y,kind);
132 Rotate(x,kind);
133 }
134 }
135 }
136 push_up(x);
137 if(goal == 0) root = x;
138 }
139 int Get_kth(int x,int k)
140 {
141 push_down(x);
142 int t = size[ch[x][0]] + 1;
143 if(t==k) return x;
144 if(t > k) return Get_kth(ch[x][0],k);
145 else return Get_kth(ch[x][1],k-t);
146 }
147 int Get_next(int x)
148 {
149 push_down(x);
150 if(ch[x][1] == 0) return -1;
151 x = ch[x][1];
152 while(ch[x][0])
153 {
154 x = ch[x][0];
155 push_down(x);
156 }
157 return x;
158 }
159 int main()
160 {
161 while(scanf("%d",&N) && N)
162 {
163 for(int i=1;i<=N;i++)
164 {
165 scanf("%d",&node[i].num);
166 node[i].id = i;
167 }
168 sort(node+1,node+N+1);
169 Init();
170 for(int i=1;i<=N;i++)
171 {
172 Splay(node[i].id,0);
173 printf("%d%s",size[ch[root][0]],i==N?"":" ");
174 Splay(Get_kth(root,i),0);
175 Splay(Get_next(node[i].id),root);
176 update_rev(Key_value);
177 }
178 printf("
");
179 }
180 }
