#include<bits/stdc++.h>
using namespace std;
const int MAXN=55;
int n,ans,up_size,down_size;
int a[MAXN],t;
vector<int> up,down;
void dfs(int now)
{
	up_size=up.size();
	down_size=down.size();
	if(up_size+down_size>=ans) return;
	if(now>n)
	{
		ans=min(ans,up_size+down_size);
//		printf("over ans:%d\n",ans);
		return;
	}
	for(int i=0;i<up_size;i++)
	{
		if(up[i]<a[now])
		{
			t=up[i];
			up[i]=a[now];
			dfs(now+1);
			up[i]=t;
			break;
		}
	}
	if(up_size==0||up[up_size-1]>=a[now])
	{
		up.push_back(a[now]);
		dfs(now+1);
		up.pop_back();
	}
	for(int i=0;i<down_size;i++)
	{
		if(down[i]>a[now])
		{
			t=down[i];
			down[i]=a[now];
			dfs(now+1);
			down[i]=t;
			break;
		}
	}
	if(down_size==0||down[down_size-1]<=a[now])
	{
		down.push_back(a[now]);
		dfs(now+1);
		down.pop_back();
	}
	return;
}
int main(){
	while (true)
	{
		scanf("%d",&n);
		if(n==0) break;
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		ans=0x7fffffff;
		up.clear();
		down.clear();
		dfs(1);
		printf("%d\n",ans);
	}
	return 0;
}