记录编号	39343	评测结果	AAAAAAAAAA
题目名称	磁性链	最终得分	100
用户昵称	wo shi 刘畅	是否通过	通过
代码语言	Pascal	运行时间	0.011 s
提交时间	2012-07-09 15:11:21	内存使用	15.43 MiB

var
   i,j,k,l,m,n,q:longint;
   f:array[0..1000,0..1000]of longint;
   a,zuo,you:array[0..1000000]of longint;

procedure sort(l,r:longint);
var
  i,j,x,y:longint;
begin
  i:=l;
  j:=r;
  x:=a[(i+j) div 2];
  repeat
    while a[i]<x do inc(i);
    while x<a[j] do dec(j);
    if i<=j then
    begin
      y:=a[i];
      a[i]:=a[j];
      a[j]:=y;
      inc(i);
      dec(j);
    end;
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j);
end;

function min(x,y:longint):longint;
begin
  if x<y then min:=x
  else min:=y;
end;

begin
  assign(input,'linka.in'); reset(input);
  assign(output,'linka.out'); rewrite(output);
  readln(m,n);
  for i:=1 to n do read(a[i]);
  sort(1,n);
  zuo[1]:=1;
  for i:=2 to n do zuo[i]:=a[i-1]+1;
  you[n]:=m;
  for i:=n-1 downto 1 do you[i]:=a[i+1]-1;
  for i:=1 to n do
   for j:=1 to n do
   f[i,j]:=maxlongint;
  for i:=1 to n do f[i,i]:=you[i]-zuo[i];
  for i:=1 to n-1 do
  begin
    j:=i+1;
    f[i,j]:=min(f[i,j-1],f[i+1,j])+you[j]-zuo[i];
  end;
  for l:=2 to n do
   for i:=1 to n-l+1 do
   begin
     j:=i+l-1;
     f[i,j]:=min(f[i+1,j],f[i,j-1])+you[j]-zuo[i];
     for k:=i+1 to j-1 do
     f[i,j]:=min(f[i,j],you[j]-zuo[i]+f[i,k-1]+f[k+1,j]);
   end;
  writeln(f[1,n]);
  close(input);
  close(output);
end.