Longest Increasing Subsequence

You are given an array of integers that may include positive numbers, negative numbers, and duplicates. Your task is to compute the Longest Increasing Subsequence (LIS) of the array. The subsequence must be strictly increasing (i.e. each element is greater than the previous one). In case of multiple solutions, any valid subsequence is accepted.

To solve this problem, you are expected to use dynamic programming. The classic algorithm has a time complexity of \(O(n^2)\), where \(n\) is the length of the array. The algorithm typically uses an additional array to keep track of the lengths of the best subsequences and a predecessor array to help reconstruct the subsequence.

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

n
a1 a2 a3 ... an

Here, n is the number of integers, and a1, a2, ..., an are the integers in the array. It is possible that \(n=0\), which indicates an empty array.

Output: The output should be printed to standard output (stdout) as follows:

L
s1 s2 ... sL

Where L is the length of the longest increasing subsequence, and s1, s2, ..., sL is the subsequence itself. When the array is empty, simply output 0.

inputFormat

The first line contains an integer n (\(0 \leq n \leq 10^5\)), which represents the number of integers in the array. The second line contains n space-separated integers.

outputFormat

The first line of the output should contain a single integer denoting the length of the longest increasing subsequence. If n > 0, the second line should contain the subsequence (space-separated). If the array is empty (n = 0), output only the number 0.

## sample

0

0

</p>