#include<bits/stdc++.h>
using namespace std;
int n;
int a[55];
bool vis[55];
vector<bool>ud;//1升序，0降序 
vector<int>t;
int ans;
void dfs(int id){
	if(ud.size()>=ans)return;
	if(id-1==n){
		ans=ud.size();
		return;
	}
	for(int i=0;i<ud.size();i++){
		if(t[i]<a[id]&&ud[i]){
			int xx=t[i];
			t[i]=a[id];
			dfs(id+1);
			t[i]=xx;
		}
		if(t[i]>a[id]&&!ud[i]){
			int xx=t[i];
			t[i]=a[id];
			dfs(id+1);
			t[i]=xx;
		}
	}
	
	int xx=ud.size();
	ud.push_back(1);
	t.push_back(a[id]);
	dfs(id+1);
	ud[xx]=0;
	dfs(id+1);
	ud.pop_back();t.pop_back();
}

void work(){
	for(int i=1;i<=n;i++){
		cin>>a[i];
		vis[i]=0;
	}
	t.clear(); ud.clear();
	ans=1e9;
	dfs(1);
	cout<<ans;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	do{
		cin>>n;
		if(n)work();
	}while(n);
	return 0;
}