#include <cstdio>
#pragma GCC optimize(2)
using namespace std;

inline int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
	while (c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-48;c=getchar();}
	return x*f;
}

const int INF=10000000;
const int MAXN=55;
int n,ans;

int h[MAXN];
int up[MAXN],down[MAXN];

inline void dfs(int a,int b,int now)
{
	if (a+b>=ans)return ;
	if (now>n)
	{
		ans=a+b;
		return ;
	}
	bool flag=false;
	int before;
	for (int i=1;i<=a;i++)
		if (h[now]>up[i])
		{
			before=up[i];
			up[i]=h[now];
			dfs(a,b,now+1);
			up[i]=before;
			flag=1;break;
		}
	if (!flag)
	{
		up[++a]=h[now];
		dfs(a,b,now+1);
		a--;
	}
	flag=false;
	for (int i=1;i<=b;i++)
		if (h[now]<down[i])
		{
			before=down[i];
			down[i]=h[now];
			dfs(a,b,now+1);
			down[i]=before;
			flag=true;break;
		}
	if (!flag)
	{
		down[++b]=h[now];
		dfs(a,b,now+1);
		b--;
	}
}

int main()
{
	while (1)
	{
		n=read();
		if (n==0)break;
		for (int i=1;i<=n;i++)h[i]=read();
		ans=INF;dfs(0,0,1);
		printf("%d\n",ans);
	}
	return 0;
}