Find the Longest Increasing Subsequence
Given an array of
n integers, you are asked to find the longest increasing subsequence of the array. If there are multiple such subsequences you can output any of them.A subsequence of an array is obtained by deleting some (possibly zero) elements of the array, without changing the order of the remaining elements. For example, if the array is , then is a subsequence of , but is not a subsequence of , since the order of the elements is not preserved.
💡
An increasing subsequence of an array is a subsequence in which the elements are in increasing order. For example, if the array is , then is an increasing subsequence of , but is not an increasing subsequence of , since the elements are not in increasing order.
Input
The first line of the input contains a single integer
n (1 ≤ n ≤ 100 000), the length of the array.The second line contains
n space-separated integers Output
The first line should contain one integer
k - the length of the longest increasing subsequence of the array.The second line should contain
k space-separated integers representing the longest subsequence itself. In case of several valid answers, you can output any of them.Examples
Input | Output |
8
1 3 2 4 5 2 6 5 | 5
1 2 4 5 6 |
6
10 9 2 5 3 7 | 3
2 5 7 |
Note
In the second example, the subsequence is also a valid increasing subsequence of length 3.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB