var f:array[0..20000] of longint;

a:array[1..200000] of longint;

n,ans,i,j,l,r,mid:longint;

xx,till:longint;

procedure init;

var i,j:longint;

begin

readln(n); fillchar(f,sizeof(f),0); ans:=maxlongint;

for i := 1 to n do

readln(a[i]);

for i:=n+1 to n+n do

a[i]:=a[i-n];

end;

begin

init;

for i:= 1 to n do

begin

fillchar(f,sizeof(f),0);

for j:= i to i+n-1 do

begin

l:=1;r:=f[0];

while l<r do

begin

mid :=(l+r)>>1;

if f[mid]<a[j] then l:=mid+1 else r:=mid;

end;

if a[j]>f[f[0]] then begin

inc(f[0]);

f[f[0]]:=a[j];

end else if a[j]<f[l] then f[l]:=a[j];

end;

if f[0]<ans then ans:=f[0];

end;

writeln(ans);

end.