program egroup;
var
  i,j,n,l,r,max,min1,min2:longint;
  a,b,c,f:array[1..30000]of longint;
procedure init;
begin
  assign(input,'egroup.in');
  reset(input);
  assign(output,'egroup.out');
  rewrite(output);
  read(n);
  for i:=1 to n do
    read(a[i]);
  for i:=1 to n do
    b[i]:=maxlongint;
  b[1]:=a[1];
  f[1]:=1
end;

procedure solve;
begin
  for i:=2 to n do
  begin
    l:=1;
    r:=i;
    while l<r do
    begin
      if b[(l+r) div 2]<=a[i] then
        l:=(l+r) div 2+1
      else r:=(l+r) div 2
    end;
    if b[l]>a[i] then
    begin
      f[i]:=l;
      b[l]:=a[i]
    end
    else
    begin
      f[i]:=l+1;
      b[l+1]:=a[i]
    end
  end;
  max:=-maxlongint;
  for i:=1 to n do
    if max<f[i] then
      max:=f[i]
end;

procedure print;
begin
  if min1>min2 then writeln(min2)
  else writeln(min1);
  close(input);
  close(output)
end;

procedure nixu;
begin
  for i:=n downto 1 do
    c[n-i+1]:=a[i];
  for i:=1 to n do
    a[i]:=c[i];
  for i:=1 to n do
    b[i]:=maxlongint;
  b[1]:=a[1];
  f[1]:=1
end;

begin
  init;
  solve;
  min1:=n-max;
  nixu;
  solve;
  min2:=n-max;
  print
end.