#include<bits/stdc++.h>
using namespace std;
struct node{
	int next,id;//id=1:升序，id=2:降序
}f[55];
int n,ans,a[55];
void dfs(int x,int s,int num)
{
	if(x>n)
	{
		if(num==0)ans=min(ans,s);
		return;
	}
	for(int i=1;i<=s;i++)
		if(f[i].id==1&&a[x]>f[i].next)
			{
				int cnt=f[i].next;
				f[i].next=a[x];
				dfs(x+1,s,num-1);
			}
		else if(f[i].id==2&&a[x]<f[i].next)
			{
				int cnt=f[i].next;
				f[i].next=a[x];
				dfs(x+1,s,num-1);
			}
	s++;
	f[s].id=1;
	f[s].next=a[x];
	dfs(x+1,s,num-1);
	s++;
	f[s].id=2;
	f[s].next=a[x];
	dfs(x+1,s,num-1);
	return;
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	while(n)
	{
		ans=n;
		for(int i=1;i<=n;i++)
			cin>>a[i];
		dfs(1,0,n);
		cout<<ans<<"\n";
		cin>>n;
	}
	return 0;
}