{
TASK:PSORT
LANG:PASCAL
}

const maxn = 50002;
      ogr = 65536;

var a, t : array[1..maxn]of longint;
    mm, i, j, n, m, k : longint;
    ind : array[0..ogr]of longint;



Function max(vv, bb : longint) : longint; begin if vv>bb then max:=vv else max:=bb; end;

Procedure add(v, st, b, c : longint);
var m : longint;
begin
  m:=b+ c div 2;
  if m=v then begin
    if ind[m]<st then ind[m]:=st;
    exit;
  end;

  if m>v then begin
    if ind[m]<st then ind[m]:=st;
    add(v, st, b, c div 2);
  end
  else begin
    add(v, st, m, c div 2);
  end;
end;


Function Find(v, b, c : longint): longint;
var m : longint;
begin
  m:=b+ c div 2;
  if m=1 then begin
    find:=ind[m];
    exit;
  end;

  if m>v then Find:=Find(v, b, c div 2)
  else
  if m=v then FInd:=ind[v]
  else
  if m<v then begin
    FInd:=max(ind[m], find(v, m, c div 2));
  end;
end;






Begin
  readln( n);
  for i:=1 to n do read( a[i]);

  t[1]:=1;
  add(a[1],1, 0, ogr);
  for i:=2 to n do begin
    k:=Find(a[i], 0, ogr);
    t[i]:=k+1;
    add(a[i], t[i], 0, ogr)
  end;
  mm:=0;
  for i:=1 to n do
    if t[i]>mm then mm:=t[i];

  writeln(n-mm);



end.


