{
TASK:psort
LANG:PASCAL
}


const ogr = 50100;
const ogr_tree = 65535;

var a : array[0..ogr] of longint;
    tree : array[0..ogr_tree] of longint;
    i, j, k, l, o, p, m, n : longint;
    fmin, max : longint;


procedure input;
var f : text;
 begin
  assign(f, '');
  reset(f);
  readln(f, n);
  for i := 1 to n do
    read(f, a[i]);
  close(f);
 end;


procedure insert(b, c, k, l : longint);
var m : longint;
 begin
  m := b + (c div 2);
  if k = m then
    begin
     if tree[m] < l then tree[m] := l;
     exit;
    end
  else if k < m then
    begin
     if tree[m] < l then tree[m] := l;
     insert(b, c div 2, k, l);
    end
  else insert(m, c div 2, k, l);
 end;

procedure less(b, c, k : longint);
var m : longint;
 begin
  m := b + (c div 2);
  if k = m then
    begin
     if tree[m] > fmin then fmin := tree[m];
     exit;
    end
  else if k > m then
    begin
     if tree[m] > fmin then fmin := tree[m];
     less(m, c div 2, k);
    end
  else less(b, c div 2, k);
 end;


begin
 input;
 for i := 1 to n do
   begin
    fmin := 0;
    less(0, ogr_tree + 1, a[i]);
    inc(fmin);
    if fmin > max then max := fmin;
    insert(0, ogr_tree + 1, a[i], fmin);
   end;
 writeln(n - max);
end.




