思路简述： 因为导弹来临是按照顺序，而非高度，所以我们绝对不能用 sort（显而易见）。

那么我们不妨将每个导弹分个类： 1、可以用某个上升拦截系统拦截。 2、可以用某个下降拦截系统拦截。 3、需要新建一个上升拦截系统拦截。 4、需要新建一个下降拦截系统拦截。 考虑其中 1 跟 2，3 跟 4 是相互矛盾的，所以我们可以剪枝优化。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=55;
int n,ans;
int a[MAXN];
vector<int> up,down;//up存上升系统，down存下降系统
void dfs(int now)//现在正在拦截第now个导弹
{
	int upsize=up.size();//注意：千万不要把它俩定义成全局变量！！血泪教训
	int downsize=down.size();//注意：千万不要把它俩定义成全局变量！！血泪教训
	if(upsize+downsize>=ans) return;//上述剪枝
	if(now>n)
	{
		ans=min(ans,upsize+downsize);//上述剪枝
//		printf("over ans:%d\n",ans);
		return;
	}
	for(int i=0;i<upsize;i++)//开始枚举每个上升系统
	{
		if(up[i]<a[now])//可以拦截
		{
			int t=up[i];//t也不可以定义为全局变量！！
            //dfs回溯备份
			up[i]=a[now];
			dfs(now+1);//继续拦截下一个
			up[i]=t;
			break;
		}
	}
	if(upsize==0||up[upsize-1]>=a[now])//判断，是否需要新开一个上升系统
	{
		up.push_back(a[now]);
		dfs(now+1);
		up.pop_back();
	}
	//同上，ctrl C,ctrl V
	//说实话，我因为复制完漏了更改名字而调了半天，太蒻了
	for(int i=0;i<downsize;i++)
	{
		if(down[i]>a[now])
		{
			int t=down[i];
			down[i]=a[now];
			dfs(now+1);
			down[i]=t;
			break;
		}
	}
	if(downsize==0||down[downsize-1]<=a[now])
	{
		down.push_back(a[now]);[DFS]
		dfs(now+1);
		down.pop_back();
	}
	return;
}
int main(){
	while (true)
	{
		scanf("%d",&n);
		if(n==0) break;//虽然题目没说，但由样例可知，n=0时结束
		up.clear();
		down.clear();
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		ans=0x7fffffff;//无穷大
		dfs(1);
		printf("%d\n",ans);
	}
	return 0;
}

/*
思路简述：
因为导弹来临是按照顺序，而非高度，所以我们绝对不能用 sort（显而易见）。

那么我们不妨将每个导弹分个类：
1、可以用某个上升拦截系统拦截。
2、可以用某个下降拦截系统拦截。
3、需要新建一个上升拦截系统拦截。
4、需要新建一个下降拦截系统拦截。
考虑其中 1 跟 2，3 跟 4 是相互矛盾的，所以我们可以剪枝优化。

剪枝代码：
int upsize=up.size();
int downsize=down.size();
if(upsize+downsize>=ans) return;//这种情况已经超过或赶上之前我的最优方案了，我还留你干嘛
if(now>n)//全部拦截后
{
	ans=min(ans,upsize+downsize);//上升下降的总套数
//	printf("over ans:%d\n",ans);
	return;
}
*/
#include<bits/stdc++.h>
using namespace std;
const int MAXN=55;
int n,ans;
int a[MAXN];
vector<int> up,down;//up存上升系统，down存下降系统
void dfs(int now)//现在正在拦截第now个导弹
{
	int upsize=up.size();//注意：千万不要把它俩定义成全局变量！！血泪教训，调了1小时
	int downsize=down.size();//注意：千万不要把它俩定义成全局变量！！血泪教训，调了1小时
	if(upsize+downsize>=ans) return;//上述剪枝
	if(now>n)
	{
		ans=min(ans,upsize+downsize);//上述剪枝
//		printf("over ans:%d\n",ans);
		return;
	}
	for(int i=0;i<upsize;i++)//开始枚举每个上升系统
	{
		if(up[i]<a[now])//可以拦截
		{
			int t=up[i];//t也不可以定义为全局变量！！
            //dfs回溯备份
			up[i]=a[now];
			dfs(now+1);//继续拦截下一个
			up[i]=t;
			break;
		}
	}
	if(upsize==0||up[upsize-1]>=a[now])//判断，是否需要新开一个上升系统
	{
		up.push_back(a[now]);
		dfs(now+1);
		up.pop_back();
	}
    //同上，ctrl C,ctrl V
    //说实话，我因为复制完漏了更改名字而调了半天，太蒻了
	for(int i=0;i<downsize;i++)
	{
		if(down[i]>a[now])
		{
			int t=down[i];
			down[i]=a[now];
			dfs(now+1);
			down[i]=t;
			break;
		}
	}
	if(downsize==0||down[downsize-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;//虽然题目没说，但由样例可知，n=0时结束
		up.clear();
		down.clear();
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		ans=0x7fffffff;//无穷大
		dfs(1);
		printf("%d\n",ans);
	}
	return 0;
}