{
TASK:psort
LANG:PASCAL
}
{$R-}
const
maxn=65536;
type
 tip=record
   i,len:longint;
  end;
var
 t:text;
 b,p:array [0..maxn+1] of longint;
 a:array [0..maxn*2+1] of tip;
 i,j,k,l,n,max:longint;
 tt:tip;
 fl:boolean;

 procedure ins(pro:tip; pos:longint);
  var
   i:longint;
   j:tip;
  begin
    i:=pos+max-1;
    a[i]:=pro;
    while i>1 do
     begin
       i:=i shr 1;
       if a[i shl 1].len>a[i shl 1+1].len then j:=a[i shl 1]
       else j:=a[i shl 1+1];
       a[i]:=j;
     end;
  end;

  procedure sub(pos:longint; var s:tip);
   var
    i,j,k:longint;
   begin
     i:=pos+max-1;
     s:=a[i];
     if pos<1 then s.i:=0 else
     while i>1 do
      begin
        k:=(i shr 1) shl 1;
        if k<>i then if s.len<a[k].len then s:=a[k];
        i:=i shr 1;
      end;
   end;
begin
{  assign(t,'psort.in');
  reset (t);}
  readln ({t,}n);
  for i:=1 to n do
   read({t,}b[i]);
{  close (t);}


  max:=1;
  while max<n do max:=max*2;

  tt.len:=1;
  tt.i:=1;
  ins(tt,1);
  for i:=2 to n do
   begin
     sub(b[i]-1,tt);
     tt.i:=i;
     tt.len:=tt.len+1;
     ins(tt,b[i]);
   end;

  writeln(n-a[1].len);
end.