#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long LL;
const int MAXN = 1e6 + 10;
const int INF = 0x3f;
int n;
int h[MAXN];
int up[MAXN], down[MAXN];
int ans;
void dfs(int step,int l,int r){
	if(l + r >= ans)return ;//如果已经比最小答案大，剪枝
	if(step == n){//遍历到结束
		ans = l + r;//保存答案
		return ;
	}
	int pla = 0;
	while(pla < l && up[pla] >= h[step]){
		pla++;
	}//求需要防最高高度
	int now = up[pla];
	up[pla] = h[step];
	if(pla < l)dfs(step + 1, l, r);
	else dfs(step + 1, l + 1, r);
	up[pla] = now;
	pla = 0;
	while(pla < r && down[pla] <= h[step]){
		pla++;
	}//求需要防最低高度
	now = down[pla];
	down[pla] = h[step];
	if(pla < r)dfs(step + 1, l, r);
	else dfs(step + 1, l, r + 1);
	down[pla] = now;
}
int main()
{
	while(cin >> n){
		if(n == 0)break;
		for(int i = 0;i < n; i++){
			cin >> h[i];
		}
		ans = n;
		dfs(0, 0, 0);//找答案
		cout << ans << endl;
	}
    return 0;
}