Longest Increasing Subsequence

Given an array of integers, your task is to find the longest subsequence of strictly increasing numbers. A subsequence is derived from the array by deleting some or no elements without changing the order of the remaining elements. If there are multiple answers, output any one of them.

The problem is a classic dynamic programming challenge and requires you to process the input from stdin and output your answer to stdout in the specified format. The solution should work efficiently even for larger arrays.

inputFormat

The first line contains an integer n which denotes the number of elements in the array. The second line contains n space-separated integers representing the array.

If n is 0, the array is empty.

outputFormat

Output the longest strictly increasing subsequence as a series of space-separated integers on a single line. If the array is empty, output an empty line.

9
10 22 9 33 21 50 41 60 80

10 22 33 50 60 80