Longest Increasing Subsequence

Given a sequence of integers, your task is to compute the Longest Increasing Subsequence (LIS).

An increasing subsequence of an array A is a sequence of indices \( i_1, i_2, \ldots, i_k \) such that \[ A[i_1] < A[i_2] < \cdots < A[i_k] \] and \(1 \leq k \leq n\). If there are multiple such subsequences of maximum length, output any one of them.

Note: The subsequence is not required to be contiguous.

Input Constraints:

• The number of integers, \(n\), satisfies \(0 \le n \le 10\,000\).
• Each integer is in the range \(-100\,000 \le A[i] \le 100\,000\).

Examples:

• Example 1: For the input sequence [10, 22, 9, 33, 21, 50, 41, 60, 80], a valid output is 10 22 33 41 60 80.
• Example 2: For the input sequence [3, 4, -1, 0, 6, 2, 3], the correct output is -1 0 2 3.

inputFormat

The input is given via standard input (stdin) in the following format:

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

If \(n = 0\), the second line may be empty, and the output should be an empty line.

outputFormat

Output the longest increasing subsequence as a sequence of space-separated integers to standard output (stdout).

If the array is empty, output an empty line.

## sample

9
10 22 9 33 21 50 41 60 80

10 22 33 41 60 80