Run #cff72ff3

def solve(arr):
    if not arr:
        return 0
    n = len(arr)
    up = [1] * n
    down = [1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:
                up[i] = max(up[i], down[j] + 1)
            elif arr[i] < arr[j]:
                down[i] = max(down[i], up[j] + 1)
    return max(up[n-1], down[n-1])