{
TASK:psort
LANG:PASCAL
}

const
  infile = '';
  outfile = '';

  lev = 16;
  maxi = 1 shl lev;

var
  f : text;

  n, i, j, l, p, r, k : longint;

  itr : array[0..maxi] of longint;
  arr : array[0..50001] of longint;

procedure ins(d, ind : longint);
begin
  p:=maxi shr 1;
  l:=p shr 1;
  k:=0;
  repeat
    if p >= ind then
    begin
      if itr[p] < d then itr[p]:=d;
      if p = ind then break;
      p:=p-l;
      l:=l shr 1;
    end
    else
      begin
        p:=p+l;
        l:=l shr 1;
      end;
    inc(k);
  until k = lev;
end;

function find(ind : longint) : longint;
begin
  r:=0;
  p:=maxi shr 1;
  l:=p shr 1;
  k:=0;
  repeat
    if p <= ind then
    begin
      if itr[p] > r then r:=itr[p];
      if p = ind then break;
      p:=p+l;
      l:=l shr 1;
    end
    else
      begin
        p:=p-l;
        l:=l shr 1;
      end;
    inc(k);
  until k = lev;
  find:=r;
end;

procedure qsort(l, r : longint);
var ll, rr, x : longint;
begin
  ll:=l; rr:=r; x:=arr[(l+r) shr 1];
end;

begin
  assign(F, infile);
  reset(f);
  readln(f, n);
  for i:=1 to n do
  begin
    read(f, j);
    arr[j]:=i;
  end;
  close(f);

  for i:=1 to n do
  begin
    if i = 8 then
     begin end;
    ins(find(arr[i]-1)+1, arr[i]);
  end;

  writeln(n-find(n));
end.
