记录编号	80956	评测结果	AAAAAAAAAAA
题目名称	[USACO Feb08] 麻烦的聚餐	最终得分	100
用户昵称	铁策	是否通过	通过
代码语言	Pascal	运行时间	0.096 s
提交时间	2013-11-07 23:02:51	内存使用	0.57 MiB

program P1398;
var
a,b,c,d:array[0..30000] of longint;
n,i,j,sum1,sum2,sum,ls,k:longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
begin
assign(input,'egroup.in');
reset(input);
assign(output,'egroup.out');
rewrite(output);
readln(n);
k:=0;
for i:=1 to n do
begin
readln(ls);
if ls<>a[k] then begin inc(k); a[k]:=ls; inc(b[k]); inc(c[k]); inc(d[k]); end
else begin inc(b[k]); inc(c[k]); inc(d[k]); end;
end;
for i:=k-1 downto 1 do
  for j:=i+1 to k do
  begin
  if a[i]<=a[j] then b[i]:=max(b[i],b[j]+d[i]);
  if a[i]>=a[j] then c[i]:=max(c[i],c[j]+d[i]);
  end;
for i:=1 to k do
if b[i]>sum then sum:=b[i];
sum1:=sum;
sum:=0;
for i:=1 to k do
if c[i]>sum then sum:=c[i];
sum2:=sum;
writeln(n-max(sum1,sum2));
end.