{
TASK: psort
LANG: Pascal
}
const
  maxn=50000;

type
  struct = object
             procedure Init;
             procedure push(k:longint);
             function say(k:longint):longint;
             a:array[1..maxn] of longint;
             l:longint;
           end;

procedure struct.Init;
begin
  l:=0;
end;

procedure struct.push(k:longint);
begin

end;

function struct.say(k:longint):longint;
begin

end;

var
   a:array[1..maxn] of longint;
   f:text;
   n:longint;



procedure inp;
var
  i:longint;
begin
   for i:=1 to n do
     read(f,a[i]);
end;

function ndnp:longint;
var
  i,j:longint;
  max:longint;
  b:array[1..maxn] of longint;
begin
  b[1]:=1;max:=1;
  for i:=2 to n do
  begin
    b[i]:=1;
    for j:=i-1 downto 1 do
    if a[j]<a[i] then
      if b[j]>=b[i] then
      begin
         b[i]:=b[j]+1;
         if b[i]>max then begin max:=b[i];break; end;
      end;
  end;
  ndnp:=max;
end;

function ndnp2:longint;
begin
end;

begin
  assign(f,'');
  reset(f);
  readln(f,n);
  if n<1000 then
  begin
   inp;
   writeln(n-ndnp);
  end else
  begin
    ndnp2;
  end;
  close(f);
end.
