Longest Increasing Subsequence

Given a sequence of integers, your task is to find the Longest Increasing Subsequence (LIS). The subsequence should maintain the order of the original list, and every element in the subsequence must be strictly greater than its previous element.

If there are multiple subsequences with the maximum length, return the one that appears first in the list.

More formally, given an array \(a = [a_1, a_2, \ldots, a_n]\), find a subsequence \( [a_{i_1}, a_{i_2}, \ldots, a_{i_k}] \) satisfying \( a_{i_1} < a_{i_2} < \cdots < a_{i_k} \) with maximum \(k\). In case of ties, choose the subsequence with the smallest starting index.

inputFormat

The input is given via standard input (stdin). The first line contains an integer \(n\), denoting the number of elements in the list. The second line contains \(n\) space-separated integers.

outputFormat

The output should be printed to standard output (stdout) as a sequence of space-separated integers representing the longest increasing subsequence. If the input list is empty, output an empty line.

## sample

9
10 22 9 33 21 50 41 60 80

10 22 33 50 60 80

</p>