思路与y总题解思路相同，$O(n2^n)$

import sys
input = lambda:sys.stdin.readline().strip()

n = 0
bomb = []
up = []
down = []
def dfs(deepth,m):
    global n
    up_n,down_n = len(up),len(down)
    if deepth < up_n + down_n:
        return False
    if m == n:
        return True
    # 放入上升
    flag = True
    for i in range(up_n):
        if up[i] < bomb[m]:
            temp = up[i]
            up[i] = bomb[m]
            if dfs(deepth,m+1):
                return True        # 找到一个可行解就退出
            up[i] = temp           # 恢复现场
            flag = False
            break                  # 只要找到能放的组，就不再试其他组了
    if flag:                       # 如果不能放入任何一个组，新建一个组
        up.append(bomb[m])
        if dfs(deepth,m+1):
            return True
        del(up[-1])                # 恢复现场
    # 放入下降，原理同上
    flag = True
    for i in range(down_n):
        if down[i] > bomb[m]:
            temp = down[i]
            down[i] = bomb[m]
            if dfs(deepth,m+1):
                return True
            down[i] = temp
            flag = False
            break
    if flag:
        down.append(bomb[m])
        if dfs(deepth,m+1):
            return True
        del(down[-1])



while True:
    n = int(input())
    if n == 0:
        break
    bomb = list(map(int,input().split()))
    deepth = 0
    up = []
    down = []
    while not dfs(deepth,0):           # 迭代加深——一层层尝试（因为答案大概率在浅层）
        deepth += 1
    print(deepth)