1 Program splay;  2 const maxn=2000008;  3 var l,r,fa,data,size:array[0..maxn] of longint;  4     num,i,rt,x,n:longint;  5 procedure init;  6 begin  7     rt:=0;  8     for i:=0 to maxn do data[i]:=-1;  9 end; 10 procedure zig(i:longint);//右旋 11 var j:longint; 12 begin 13     j:=fa[i]; 14     l[j]:=r[i]; 15     if l[j]<>0 then fa[l[j]]:=j; 16     fa[i]:=fa[j]; 17     if fa[i]<>0 then 18     if j=l[fa[i]] then     l[fa[i]]:=i 19                   else    r[fa[i]]:=i; 20     fa[j]:=i; 21     r[i]:=j; 22         size[j]:=size[l[j]]+size[r[j]]+1; 23     size[i]:=size[l[i]]+size[r[i]]+1; 24 end; 25 procedure zag(i:longint);//左旋 26 var j:longint; 27 begin 28     j:=fa[i]; 29     r[j]:=l[i]; 30     if r[j]<>0 then fa[r[j]]:=j; 31     fa[i]:=fa[j]; 32     if fa[i]<>0 then 33     if j=l[fa[i]] then l[fa[i]]:=i 34                 else r[fa[i]]:=i; 35     fa[j]:=i; 36     l[i]:=j; 37         size[j]:=size[l[j]]+size[r[j]]+1; 38     size[i]:=size[l[i]]+size[r[i]]+1; 39 end; 40 procedure splay(x:longint); 41 var y:longint; 42 begin 43     while fa[x]<>0 do 44     begin 45         y:=fa[x]; 46         if fa[y]=0 then 47         begin 48             if x=l[y] then zig(x) 49                       else zag(x); 50             break; 51         end; 52         if x=l[y] then 53             if y=l[fa[y]] then begin zig(y); zig(x); end 54                           else begin zig(x); zag(x); end 55         else 56             if y=r[fa[y]] then begin zag(y); zag(x); end 57                           else begin zag(x); zig(x); end; 58     end; 59     rt:=x; 60 end; 61 procedure insert(x:longint); 62 var p:longint; 63 begin 64     inc(num); 65     data[num]:=x; size[num]:=1; 66     if rt=0 then begin rt:=num; exit; end; 67     p:=rt; 68     while true do 69     begin 70         if x<data[p] then 71         begin 72             if l[p]=0 then 73             begin 74                 fa[num]:=p; 75                 l[p]:=num; 76                                 break; 77             end    else p:=l[p]; 78         end 79         else 80         begin 81             if r[p]=0 then 82             begin 83                 fa[num]:=p; 84                 r[p]:=num; 85                                 break; 86             end else p:=r[p]; 87         end; 88     end; 89     splay(num); 90 end; 91 function search(x,p:longint):longint;//查找值为x的结点，如果找到返回所在结点，没找到返回0 92 begin 93     if (data[p]=-1) or (x=data[p]) then exit(p); 94     if x<data[p] then exit(search(x,l[p])) 95                  else exit(search(x,r[p])); 96 end; 97 function find(x:longint):longint;//x为查找的值 y为值所在的节点 找到返回节点 没找到返回-1 splay内部操作 98 var p:longint; 99 begin100     p:=search(x,rt);101     if data[p]=-1 then exit(-1);102     splay(p);103     exit(p);104 end;105 function findmin(p:longint):longint;//找以p为根结点的子树中的最小值106 begin107     while l[p]<>0 do p:=l[p];108     splay(p);109     exit(data[p]);110 end;111 function findmax(p:longint):longint;//找以p为根结点的子树中的最大值112 begin113     while r[p]<>0 do p:=r[p];114     splay(p);115     exit(data[p]);116 end;117 function findpred(x:longint):longint;//找某个值的前趋118 var p:longint;119 begin120     p:=find(x);121     exit(findmax(l[p]));122 end;123 function findsucc(x:longint):longint;//找某个值的后继124 var p:longint;125 begin126     p:=find(x);127     exit(findmin(r[p]));128 end;129 procedure join(x,y:longint);//合并130 var p:longint;131 begin132     if x=0 then begin rt:=y; fa[y]:=0; exit; end;133     if y=0 then begin rt:=x; fa[x]:=0; exit; end;134     p:=findmax(x);135     r[p]:=y; fa[y]:=p;136     rt:=p;137 end;138 procedure delete(x:longint);139 var p:longint;140 begin141     p:=find(x);142     join(l[p],r[p]);143         l[p]:=0; r[p]:=0;144 end;145 function found(x,now:longint):longint;//找第k大的数146 begin147     if x=size[r[now]]+1 then exit(data[now]);148     if x>size[r[now]]+1 then exit(found(x-size[r[now]]-1,l[now]));149     if x<size[r[now]]+1 then exit(found(x,r[now]));150 end;151 begin152     init;153     readln(n);154     for i:=1 to n do155     begin156         read(x);157         insert(x);158     end;159     for i:=1 to n do write(found(n-i+1,rt),‘ ‘);160 end.