lt = []
cnt = 0
u = 0
up = [0] * 55
down = [0] * 55

def bfs(n,su,sd):
    global lt, cnt, up, down, u
    if su + sd >= cnt:
        return 
    if n == u:
        cnt = su + sd 
        return 
    # up
    k = 0
    while k < su and up[k] >= lt[n]:
        k += 1
    t = up[k]
    up[k] = lt[n]
    if k >= su:
        bfs(n+1,su+1,sd)
    else:
        bfs(n+1,su,sd)
    up[k] = t

    # down
    k = 0
    while k < sd and down[k] <= lt[n]:
        k += 1
    t = down[k]
    down[k] = lt[n]
    if k >= sd:
        bfs(n+1,su,sd+1)
    else:
        bfs(n+1,su,sd)
    down[k] = t


while True:
    u = int(input())
    if u==0:
        break
    lt = list(map(int,input().split()))
    cnt = u
    bfs(0,0,0)
    print(cnt)