program shells;
type //vektor=^longint;
     vektor=array[0..500002] of longint;
var n,i:longint;
    be,ki:text;
    v:vektor;
    readbuf,writebuf:array[0..65000] of byte;
    r,vr:boolean;

procedure shellsort;
var inc,i,j:longint;
    tmp:longint;
begin
 inc:=trunc(n / 2.71828 );
 while inc >= 1 do
   begin
    for i:=inc+1 to n do
      begin
       tmp:=v[i];
       j:=i;
       while (j >= inc)and(v[j-inc]>tmp) do
          begin
           v[j]:=v[j-inc];
           j:=j-inc;
          end;
       v[j]:=tmp;
      end;
    if inc < 11 then
       if inc=1 then
         inc:=0
        else inc:=1
     else inc:=trunc(inc / 2.71828);
   end;
end;

begin
 assign(be,'algsort.in');
 assign(ki,'algsort.out');
 setTextBuf(be,readbuf);
 SetTextBuf(ki,writebuf);
 reset(be);
 rewrite(ki);
 readln(be,n);
 r:=true;
 vr:=true;
 read(be,v[1]);
 for i:=2 to n do
   begin
    read(be,v[i]);
    if v[i] >= v[i-1] then
        vr:=false;
    if v[i] <= v[i-1] then
        r:=false;
   end;
 if r then
   begin
    for i:=1 to n do
      write(ki,v[i],' ');
    close(ki);
    halt(0);
   end;
 if vr then
   begin
    for i:=n downto 1 do
      write(ki,v[i],' ');
    close(ki);
    halt(1);
   end;
 shellsort;
 for i:=1 to n do
  write(ki,v[i],' ');
 close(ki);
end.