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.

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 (), representing the elements of the array.

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

Note

In the second example, the subsequence is also a valid increasing subsequence of length 3.