Longest Increasing Subsequence

Given an array of integers, your task is to find the longest increasing subsequence (LIS) from the array.

An increasing subsequence is a sequence that can be derived from the array by deleting some (or no) elements without changing the order of the remaining elements. For example, if the input array is [10, 22, 9, 33, 21, 50, 41, 60], one possible longest increasing subsequence is [10, 22, 33, 50, 60].

The dynamic programming recurrence used to calculate the length is given by $$ dp[i] = \max_{0 \leq j arr[j]}\{dp[j]\} + 1, $$ where dp[i] represents the length of the LIS ending at position i.

If there are multiple valid answers, you may output any one of them.

inputFormat

The input is read from standard input. The first line contains a single integer n (the number of elements in the array). The second line contains n space-separated integers.

\(1 \leq n \leq 10^5\) (Note: n can be large, but the intended solution uses an O(n^2) approach which is sufficient for the provided test cases.)

outputFormat

Print the longest increasing subsequence from the array on a single line as space-separated integers.

8
10 22 9 33 21 50 41 60

10 22 33 50 60