Longest Increasing Subsequence

Given a sequence of integers, your task is to find the longest strictly increasing subsequence (LIS) from the given list. A subsequence is derived by deleting some or no elements without changing the order of the remaining elements. The subsequence must be strictly increasing (i.e. for every two consecutive elements, the latter is greater than the former).

Note: If there are multiple answers, you may output any one. The input is taken from standard input (stdin) and the result should be printed to standard output (stdout).

Mathematical formulation:

Given an array \(a[0 \dots n-1]\), find a subsequence \(a[i_1], a[i_2], \dots, a[i_k]\) such that \(a[i_1] < a[i_2] < \cdots < a[i_k]\) and \(k\) is maximized.

inputFormat

The input is read from the standard input (stdin). The first line contains an integer \(n\) indicating the number of elements in the sequence. The second line contains \(n\) space-separated integers.

outputFormat

Output the elements of the longest increasing subsequence on separate lines to standard output (stdout).

## sample

9
2 1 3 2 2 4 3 5 2

1
2
3
5

</p>