/*
        题目分析 ： 
                    注意点 : 1) 本题区别于上一题的第一点，本题有多组数据
                             2) 本题需要求一下同时走两个方向的最少需要的序列个数

                    分析 : 看范围      50 显然这道题可以用暴搜的方式来解决

                    3) 我们只需要求一下最小、长上升子序列和最长下降子序列同时进行需要多少个序列才能把整个序列包含即可

                        3-1) 包搜记得恢复现场 和合理的减枝




*/



#include <iostream>
#include <cstring>

using namespace std;

const int N = 55;
int up[N] , down[N] , h[N];

int n;

int ans;
void dfs(int u ,int sd ,int su) {
    if (sd + su >= ans) return;  // 减枝 : 如果sd + su 的值 >= ans 那么该种情况可以去除，因为最多只需要ans个
    if (u == n) {  //如果 u == n 表示遍历完毕
        ans = sd + su;
        return;
    }

    int k = 0;

        while (k < sd && up[k] <= h[u]) k ++;
        int t = up[k];
        up[k] = h[u];
        if (k < sd) dfs(u + 1,sd,su); //加入到已经存在的上升子序列中
        else dfs(u + 1,sd + 1,su);
        up[k] = t; // 恢复现场


        k = 0;

        while (k < su && down[k] >= h[u]) k ++;
         t = down[k];
        down[k] = h[u];
        if (k < su) dfs(u + 1,sd,su); //加入到已经存在的下降子序列中
        else dfs(u + 1,sd,su + 1);
        down[k] = t; // 恢复现场


}
int main() {

    while (cin >> n , n) {
        for (int i = 0 ; i < n ; i ++ ) cin >> h[i];
        ans = n;

        dfs(0,0,0);
        cout << ans << endl;
    }

}