{
TASK: psort
LANG: PASCAL
}
const
 maxn = 60001;
var
 a : array[0..maxn] of longint;
 ln : array[0..maxn] of longint;
 i,n,k,l,r,m : longint;
procedure init;
var f : text;
begin
   assign(f,'');
   reset(f);
   readln(f,n);
   for i:=1 to n do
   read(f,a[i]);
end;
procedure main;
begin
   ln[1]:=a[1];
   k:=1;
   for i:=2 to n do
   begin
      if a[i]<ln[1] then ln[1]:=a[i]
      else
      if a[i]>ln[k] then
      begin
         inc(k);
         ln[k]:=a[i];
      end
      else
      begin
         l:=1;
         r:=k;
         while l<r-1 do
         begin
            m:=(l+r) div 2;
            if ln[m]>=a[i] then r:=m-1
            else
            l:=m;
         end;
         ln[r]:=a[i];
      end;
   end;
end;
procedure outp;
begin
   writeln(n-k);
end;
begin
   init;
   main;
   outp;
end.
