var cd:array[1..100005] of record ai,aj:longint end;
    t:array[1..100005] of longint;
    n,i,j,a,b,c,aux,st,dr:longint;

 procedure lee(q,p:longint);
  begin
   inc(b);
   cd[b].ai:=q;
   cd[b].aj:=p
  end;

begin
assign(input,'algsort.in'); reset(input);
assign(output,'algsort.out'); rewrite(output);
readln(n);
for i:=1 to n do read(t[i]);
a:=0; b:=1;
cd[b].ai:=1; cd[b].aj:=n;
repeat
 inc(a);
 i:=cd[a].ai; st:=i;
 j:=cd[a].aj; dr:=j;
 c:=t[(i+j) div 2];
 repeat
  while t[i]<c do inc(i);
  while t[j]>c do dec(j);
  if i<=j then
   begin
    aux:=t[i];
    t[i]:=t[j];
    t[j]:=aux;
    inc(i);
    dec(j)
   end
 until i>j;
  if st<j then lee(st,j);
  if i<dr then lee(i,dr)
until a=b;
for i:=1 to n do write(t[i],' ');
close(input);
close(output)
end.