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