Longest Increasing Subsequence 4

A sequence $A$ is given. Pick some elements of $A$, keep their original order, and join them: the result is a subsequence of $A$. If the values of that subsequence always grow from left to right, it is an increasing subsequence.

Write a program that finds a longest increasing subsequence of $A$ and prints its length together with its elements.

For example, if $A = \{10, 20, 10, 30, 20, 50\}$, a longest increasing subsequence takes the first, second, fourth, and sixth elements, giving $\{10, 20, 30, 50\}$ with length $4$.

There can be several increasing subsequences of maximum length. In that case only the lexicographically smallest one counts as the answer. Between two sequences of the same length, compare values from the front: the one with the smaller value at the first position where they differ is lexicographically smaller.

The first line contains the length $N$ of the sequence $A$. ($1 \le N \le 1{,}000$)

The second line contains the elements $A_1, A_2, \dots, A_N$ separated by spaces. ($1 \le A_i \le 1{,}000$)

Print the length of a longest increasing subsequence of $A$ on the first line.

Print the elements of that subsequence on the second line, in order, separated by single spaces. If several increasing subsequences have the maximum length, print the lexicographically smallest one.