Longest Increasing Subsequence

Given a sequence of integers, your task is to compute the longest increasing subsequence (LIS). The longest increasing subsequence of a sequence is a subsequence that is strictly increasing and has the maximum possible length. Formally, given a sequence (a_1, a_2, \dots, a_n), find a subsequence (a_{i_1}, a_{i_2}, \dots, a_{i_k}) where (1 \le i_1 < i_2 < \dots < i_k \le n) and (a_{i_1} < a_{i_2} < \dots < a_{i_k}), and (k) is as large as possible.

If there are multiple longest increasing subsequences, you can output any one of them.

Note: The input is given on standard input and the result should be printed to standard output. All numbers in the output must be space-separated.

inputFormat

The first line contains an integer (n), which is the number of elements in the sequence. The second line contains (n) space-separated integers representing the sequence.

outputFormat

Output the longest increasing subsequence as a sequence of space-separated integers on a single line. If the input sequence is empty, output an empty line.## sample

9
10 22 9 33 21 50 41 60 80

10 22 33 50 60 80