记录编号	21013	评测结果	AAAAAAAAAA
题目名称	488.奇怪的监狱	最终得分	100
用户昵称	wo shi 刘畅	是否通过	通过
代码语言	Pascal	运行时间	0.020 s
提交时间	2010-11-02 15:47:04	内存使用	3.94 MiB

var
  p,q,i,l,k,j:longint;
  a:array[0..1000]of longint;
  f:Array[0..1000,0..1000]of longint;

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

procedure init;
var
  i:longint;
begin
  readln(p,q);
  for i:=1 to q do read(a[i]);
  a[q+1]:=p+1;
end;

begin
  assign(input,'prison.in'); reset(input);
  assign(output,'prison.out'); rewrite(output);
  init;
  sort(1,q);
  for l:=0 to q-1 do
   for i:=1 to q-l do
   begin
     j:=i+l;
     f[i,j]:=maxlongint;
     for k:=i to j do
      if f[i,k-1]+f[k+1,j]<f[i,j] then
      f[i,j]:=f[i,k-1]+f[k+1,j];
     f[i,j]:=f[i,j]+a[j+1]-a[i-1]-2;
   end;
  writeln(f[1,q]);
  close(input);
  close(output);
end.