//枚举顺序：先枚举将该导弹放入上升子序列还是下降子序列
//第二步：若放到上升子序列的后面，那么就枚举放到哪个上升子序列的后面
//若放到下降子序列的后面，那么就枚举放到哪个下降子序列的后面。


#include<iostream>
#include<cstring>

using namespace std;
const int N=53;
int dom[N];
int up[N],down[N];//分别用来存放每个上升子序列或下降子序列的末尾元素的值
int n;


bool dfs(int depth,int u,int su, int sd)
{
    //u 表示当前枚举到第几个数字，su为上升子序列的个数，sd为下降子序列的个数

    if(su+sd>depth) return false;
    if(u==n) return true;//枚举到最后， 返回true

    //枚举放到上升子序列
    bool flag1=false;
    for(int i=1;i<=su;i++)
    {
        if(dom[u]>up[i])
        {
            int t=up[i];//方便恢复现场
            up[i]=dom[u];
            if(dfs(depth,u+1,su,sd)) return true;
            up[i]=t;
            flag1=true;//true表示 放到了上升子序列，没有另开一个新的序列]]
            break;
        }
    }
    if(!flag1)
    {
        //flag1为假说明没有放到已经有的序列当中去
        up[su+1]=dom[u];
        if(dfs(depth,u+1,su+1,sd)) return true;
    }

    //枚举下降子序列
    flag1=false;
    for(int i=1;i<=sd;i++)
    {
        if(dom[u]<down[i])
        {
            int t=down[i];
            down[i]=dom[u];
            if(dfs(depth,u+1,su,sd)) return true;
            down[i]=t;
            flag1=true;
            break;
        }
    }

    if(!flag1)
    {
        down[sd+1]=dom[u];
        if(dfs(depth,u+1,su,sd+1)) return true;
    }

    return false;


}
int main()
{
    while(scanf("%d",&n)==1&&n)
    {
        for(int i=0;i<n;i++)
        cin>>dom[i];

        int depth=0;
        while(!dfs(depth,0,0,0)) depth++;

        cout<<depth<<endl;

    }

    return 0;

}