program ex(input,output);
var i,j,k,m,n,best:integer;
  a:array[1..100] of integer;
  d:array[1..100,1..100] of integer;
  store:array[1..100,1..100] of integer;
  available: array[1..100] of integer;    
  forbid : array[1..100] of integer;
  count:integer;
function out : integer;
var i:integer;
var c: integer;
begin
  c:=0;
  for i:=1 to n do write(a[i]:2);
  readln; {riteln;}
  for i:=1 to n do c:=c+d[a[i],a[i+1]];
  c:=c+d[a[n], a[1]];
  {writeln('c=',c, ' best= ', best);}
  if c<best then best:=c;
  out:=c;
end;
function eval(k:integer):integer;
var i,s:integer;
begin
  s:=0;
  for i:=1 to k do s:=s+d[a[i-1],a[i]];
  eval:=s;
end;
procedure swap(i,j:integer);
var w:integer;
begin
{  writeln('i ', i,' j ', j);}
  w:=a[i]; a[i]:=a[j]; a[j]:=w;
  count:=count+1;
  if best<eval(i) then best:=eval(i);
end;
function minimum(k:integer):integer;
var i,j,temp:integer;
begin
  j:=0; temp:=99;
  for i:=k to n do
    if (a[i]<temp) and (a[i]>a[k-1]) then begin
      temp:=a[i]; j:=i
    end;
  minimum:=j;
end;
procedure save(k:integer);
var i:integer;
begin
  for i:=k to n do store[k,i]:=a[i];
end;
procedure recover(k:integer);
var i:integer;
begin
  for i:=k to n do a[i]:=store[k,i];
end;
procedure reverse(k:integer);
var i:integer;
begin
  for i:=k to (k+n-1) div 2 do swap(i, n-i+k);
end;
procedure perm(k, partial:integer);
var i,j, cost:integer;
begin
  if k<=n-1 then 
    for i:=k to n do begin
      cost:=eval(k); {writeln('cost ',cost);}
      save(k);
      if cost<best then begin  perm(k+1,cost) end;
      if i<>n then begin
{         if cost<best then reverse(k+1);}
        recover(k);
        j:=minimum(k+1);
        swap(k,j); out 
      end
    end;
  {out;}
end;
begin {main program}
   d[1,1]:=0; d[1,2]:=5; d[1,3]:=99; d[1,4]:=1; d[1,5]:=2;
   d[2,1]:=2; d[2,2]:=0; d[2,3]:=2; d[2,4]:=1; d[2,5]:=4;
   d[3,1]:=3; d[3,2]:=1; d[3,3]:=0; d[3,4]:=3; d[3,5]:=9;
   d[4,1]:=4; d[4,2]:=3; d[4,3]:=2; d[4,4]:=0; d[4,5]:=7;
   d[5,1]:=2; d[5,2]:=1; d[5,3]:=5; d[5,4]:=3; d[5,5]:=0;
   readln(n);
   for i:=1 to n do a[i]:=i;
   forbid[2]:=3;
   best:=999;
   out;
   count:=0;
   perm(1, 0);
   out;
   writeln('count= ',count);
   readln
end.