def solve_lis(arr):
    n = len(arr)
    best = [0] * (n+1)
    best[n-1] = 1

    # step 1 we'll compute the best array using Dynamic Programming
    for i in range(n-2, -1, -1):
        max = 0
        temp = arr[i]
        for j in range(i+1, n):
            if arr[j] > arr[i] and best[j] > max:
                max = best[j]
        best[i] = 1 + max

    maxEl = best[0]
    maxPos = 0
    for i in range(1, n):
        if best[i] > maxEl:
            maxEl = best[i]
            maxPos = i
    print(arr[maxPos], end = " ")
    maxEl -= 1
    for k in range(maxPos+1, n):
        if best[k] == maxEl and arr[maxPos] < arr[k]:
            print("%d "%arr[k], end =" ")
            maxEl-=1
def func():
    # let we have the following array
    arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]

    solve_lis(arr)

func()