using namespace std;
int a[55],f[55],lst[55],ans;
void dfs(int x,int cnt){
	if(cnt>=ans)return;
	if(x==a[0]+1){
		ans=min(ans,cnt);
		return;
	}
	int maxn=-1e9,minn=1e9,pos1,pos2;
	for(int i=1;i<=cnt;i++){
		if(f[i]==1&&lst[i]>maxn&&lst[i]<a[x]){
			maxn=lst[i];
			pos1=i;
		}
		if(f[i]==-1&&lst[i]<minn&&lst[i]>a[x]){
			minn=lst[i];
			pos2=i;
		}
	}
	if(maxn!=-1e9){
		int tmp=lst[pos1];
		lst[pos1]=a[x];
		dfs(x+1,cnt);
		lst[pos1]=tmp;
	}
	if(minn!=1e9){
		int tmp=lst[pos2];
		lst[pos2]=a[x];
		dfs(x+1,cnt);
		lst[pos2]=tmp;
	}
	for(int i=1;i<=cnt;i++){
		if(f[i]==0){
			if(a[x]>lst[i]&&lst[i]<=maxn||a[x]<lst[i]&&lst[i]>=minn)continue;
			if(lst[i]!=a[x]){
				int tmp=lst[i];
				if(a[x]>lst[i])f[i]=1;
				else f[i]=-1;
				lst[i]=a[x];
				dfs(x+1,cnt);
				f[i]=0;
				lst[i]=tmp;
			}	
		}
	}
	lst[cnt+1]=a[x];
	dfs(x+1,cnt+1);
	lst[cnt+1]=0x3f3f3f3f;
}
int main(){
	while(cin>>a[0]&&a[0]){
		ans=a[0];
		for(int i=1;i<=a[0];i++)cin>>a[i];
		memset(lst,0x3f,sizeof(lst));
		memset(f,0,sizeof(f));
		dfs(1,0);
		cout<<ans<<endl;
	}
	return 0;
}

rt