Longest Increasing Subsequence

You are given an integer n and a sequence of n integers. Your task is to compute the length and one example of the longest strictly increasing subsequence (LIS) in the sequence.

The solution is expected to implement dynamic programming. In particular, the recurrence used is given by:

$$dp[i] = \max_{0 \le j seq[j]} \{dp[j]\} + 1.$$

If there are multiple valid answers, outputting any one of them is acceptable.

inputFormat

The input is read from standard input (stdin). The first line contains an integer n representing the length of the sequence. The second line contains n space-separated integers representing the sequence.

Example:

8
5 2 8 6 3 6 9 7

outputFormat

The output is written to standard output (stdout). The first line should contain a single integer denoting the length of the longest increasing subsequence. The second line should contain the subsequence itself, with the elements separated by a single space.

Example:

4
2 3 6 9

## sample

8
5 2 8 6 3 6 9 7

4
2 3 6 9

</p>