map<int,int>m;
int@n,b[n],c[n];
m[0]=-1;
m[n+1]=-1;
rep(k,n){
	int@a;
	auto i=m.upper_bound(a);
	auto j=prev(i);
	m[a]=b[k]=max(i->second,j->second)+1;
	c[k]=i->first-j->first-2;
}
wt(b(n));
wt(c(n));