#include #include #include #include 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; }