EGROUP PASCAL

const   vc=trunc(1e9);
var     a,f,g,b,t,ds:array[0..100000] of longint;
        resf,resg,n,k,i,max,res:longint;

procedure nhap;
var i:longint;
begin
    read(n);
    for i:=1 to n do readln(a[i]);
end;

function bsf(x,l,r:longint):longint;
var res,m:longint;
begin
    res:=0;
    while l<=r do
    begin
        m:=(l+r) div 2;
        if (a[b[m]]>=x) then
        begin
            res:=m;
            l:=m+1;
        end
        else r:=m-1;
    end;
    exit(res);
end;

procedure tim_f;
var i,j,jmax,z,d:longint;
begin
    f[1]:=1;res:=1; b[1]:=1;
    for i:=2 to n do
       begin
        k:=bsf(a[i],1,f[res]);
        f[i]:=k+1;
        t[i]:=b[k];
           if f[res]<f[i] then res:=i;//max:=0;
            b[f[i]]:=i;
       end;
    //writeln(f[res]);
    resf:=f[res];
    //truyvet(res);
end;

function bsg(x,l,r:longint):longint;
var res,m:longint;
begin
    res:=0;
    while l<=r do
    begin
        m:=(l+r) div 2;
        if (a[b[m]]<=x) then
        begin
            res:=m;
            l:=m+1;
        end
        else r:=m-1;
    end;
    exit(res);
end;

procedure tim_g;
var i,j,jmax,z,d:longint;
begin
    g[1]:=1;res:=1; b[1]:=1;
    for i:=2 to n do
       begin
        k:=bsg(a[i],1,g[res]);
        g[i]:=k+1;
        t[i]:=b[k];
           if g[res]<g[i] then res:=i;//max:=0;
            b[g[i]]:=i;
       end;
  //writeln(g[res]);d:=0;
    resg:=g[res];
    //truyvet(res);
end;


procedure solve;
begin
    tim_f;
    tim_g;
    if resf<resg then
        writeln(n-resg)
    else
        writeln(n-resf);

end;

begin
    assign(input,'egroup.inp');reset(input);
    assign(output,'egroup.out');rewrite(output);
    nhap;
    solve;
end.