ll n,k,r,x,a[1d5],b[1d5],c[4d5];{rd(n,a(n));rep(d,4){rep(i,n)b[k=lower_bound(b,b+r,x=a[d&1?n+~i:i]*(d%3?-1:1))-b]=x,c[d*n+i]=r+=r==k;r=0;}r>?=min(c[0..2n],c[4n-(1..)]);wt(r-1);}