Longest Increasing Subsequence

Given a sequence of integers, your task is to find and output the Longest Increasing Subsequence (LIS) in the given list. A subsequence is a sequence that can be derived from the list by deleting some or no elements without changing the order of the remaining elements. The subsequence should be strictly increasing, i.e., for any two consecutive elements \(a\) and \(b\) in the subsequence, it must hold that \(a < b\).

Formally, given a list \(L = [a_1,a_2,\dots,a_n]\), find a subsequence \(S = [a_{i_1},a_{i_2},\dots,a_{i_k}]\) such that \(1 \le i_1 < i_2 < \dots < i_k \le n\) and \(a_{i_1} < a_{i_2} < \dots < a_{i_k}\) with \(k\) as large as possible.

You need to maintain the relative order of the elements as in the original list. If there are multiple valid solutions, output any one of them.

inputFormat

The first line contains an integer \(n\) representing the number of elements in the list. The second line contains \(n\) space-separated integers representing the list.

outputFormat

Output the longest increasing subsequence as a sequence of space-separated integers. If the list is empty, output nothing.

9
10 22 9 33 21 50 41 60 80

10 22 33 50 60 80