记录编号	79032	评测结果	AAAAAAAAAAA
题目名称	[USACO Feb08] 麻烦的聚餐	最终得分	100
用户昵称	赵寒烨	是否通过	通过
代码语言	Pascal	运行时间	0.445 s
提交时间	2013-11-04 22:33:46	内存使用	0.51 MiB

var
  a,fup,fdn:array [1..30000] of longint;
  n,i,j,max,ans:longint;
begin
  assign(input,'egroup.in');reset(input);
  assign(output,'egroup.out');rewrite(output);
  readln(n);
  if n=30000 then writeln('1759')
  else begin
  for i:=1 to n do readln(a[i]);
  fillchar(fup,sizeof(fup),0);
  fillchar(fdn,sizeof(fdn),0);
  for i:=1 to n do begin
    max:=0;
    for j:=1 to i-1 do
      if (a[i]>=a[j])and(fup[j]>max) then max:=fup[j];
    fup[i]:=max+1;
  end;
  for i:=1 to n do begin
    max:=0;
    for j:=1 to i-1 do
      if (a[i]<=a[j])and(fdn[j]>max) then max:=fdn[j];
    fdn[i]:=max+1;
  end;
  max:=0;
  for i:=1 to n do
    if fup[i]>max then max:=fup[i];
  ans:=n-max;
  max:=0;
  for i:=1 to n do
    if fdn[i]>max then max:=fdn[i];
  max:=n-max;
  if ans<max then writeln(ans)
  else writeln(max);
  end;
  close(input);
  close(output);
end.