记录编号	14403	评测结果	AAAAAAAAAA
题目名称	抢修道路	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	Pascal	运行时间	0.535 s
提交时间	2009-10-29 15:46:31	内存使用	0.16 MiB

program xmz;
var
f1,f2:text;
q,x:array[0..2001]of longint;
f,d:array[0..2001]of int64;
a,b,n:longint;
min:int64;
procedure px(l,r:longint);
var i,j,tmp,mid:longint;
begin
i:=l;j:=r;mid:=q[(l+r) shr 1];
repeat
while q[i]<mid do inc(i);
while mid<q[j] do dec(j);
if i<=j then
begin
tmp:=q[i];
q[i]:=q[j];
q[j]:=tmp;
inc(i);dec(j);
end;
until i>j;
if l<j then px(l,j);
if i<r then px(i,r);
end;

begin
 assign(f1,'roady.in');assign(f2,'roady.out');
 reset(f1);rewrite(f2);
 read(f1,n);
 for a:=1 to n do
  begin
   read(f1,x[a]);
   q[a]:=x[a];
  end;
  px(1,n);

 for a:=1 to n do
  begin
   d[0]:=f[1];
   for b:=1 to n do
    begin d[b]:=d[b-1]; if f[b]<d[b] then d[b]:=f[b];end;
   for b:=n downto 1 do
    f[b]:=d[b]+abs(q[b]-x[a]);
  end;
  min:=999999999;
 for a:=1 to n do
  if f[a]<min then min:=f[a];

 fillchar(f,sizeof(f),0);


 for a:=1 to n do
  begin
   d[n+1]:=f[n];
   for b:=n downto 1 do
    begin d[b]:=d[b+1]; if f[b]<d[b] then d[b]:=f[b];end;
   for b:=n downto 1 do
    f[b]:=d[b]+abs(q[b]-x[a]);
  end;

 for a:=1 to n do
  if f[a]<min then min:=f[a];

 writeln(f2,min);
 close(f1);close(f2);
end.