记录编号	39359	评测结果	AAAAAAAAAA
题目名称	磁性链	最终得分	100
用户昵称	czp	是否通过	通过
代码语言	Pascal	运行时间	0.044 s
提交时间	2012-07-09 16:03:09	内存使用	4.07 MiB

var
 i,j,n,q,tp:longint;
 a:array[1..122] of longint;
 f:array[0..1011,0..1011] of longint;
 procedure dfs(l,r:longint);
 var i,j,k,ct:longint;
 begin
  if f[l,r]>-1 then exit;
  if l>r then begin f[l,r]:=0;exit; end;
  f[l,r]:=maxlongint div 3;
  ct:=0;
  for i:=1 to q do
   begin
    if a[i]>r then break;
    if (l<=a[i]) then
     begin
      inc(ct);
      dfs(l,a[i]-1);
      dfs(a[i]+1,r);
      if f[l,r]>f[l,a[i]-1]+f[a[i]+1,r] then
      f[l,r]:=f[l,a[i]-1]+f[a[i]+1,r];
     end;
   end;
  if ct=0 then f[l,r]:=0 else f[l,r]:=f[l,r]+r-l;
 end;
begin
 assign(input,'linka.in');reset(input);
 assign(output,'linka.out');rewrite(output);
 readln(n,q);
 for i:=1 to q do
  read(a[i]);
 readln;
 for i:=1 to q do
  for j:=1 to q-i do
   begin
    if a[j]>a[j+1] then
     begin
      tp:=a[j];
      a[j]:=a[j+1];
      a[j+1]:=tp;
     end;
   end;
 fillchar(f,sizeof(f),$ff);
 dfs(1,n);
 writeln(f[1,n]);
 close(input);close(output);
end.