Longest Increasing Subsequence

You are given an array of N integers. Your task is to compute the longest increasing subsequence (LIS) of the array. The subsequence is not necessarily contiguous, but the order of elements must remain the same as in the original array.

The Longest Increasing Subsequence is defined as the longest sequence of indices i₁, i₂, ..., i_k such that array[i1] < array[i2] < ... < array[ik] with 1 ≤ i1 < i2 < ... < ik ≤ N.

If there are multiple answers, you can output any one of them as long as the subsequence is increasing and its length is maximum possible.

Note: If the array is empty, output 0 on the first line and an empty second line.

inputFormat

The first line contains an integer N — the size of the array.

The second line contains N space-separated integers — the elements of the array.

outputFormat

Output two lines:

• The first line contains an integer representing the length of the longest increasing subsequence.
• The second line contains the elements of the subsequence separated by a single space. If the subsequence is empty, output an empty line.

## sample

6
5 2 8 6 3 6

3
2 3 6

</p>