题目描述

输入一个数组，找到最长的上升子序列（子序列可以不连续）并输出。

例如，数组a = {1, 2, 3, -1, -2, 7, 9}，它的最长上升子序列是{1, 2, 3, 7, 9}，长度为5。另外，还有一些子序列是上升子序列，比如{1, 2, 3}，{-2, 7, 9}等，但都不是最长的。

输入格式

第一行一个正整数n(1≤n≤100)，代表数组长度；

第二行n个正整数ai(-100≤ai≤100)，代表数组的每个元素。

输出格式

若干个整数，为最长上升子序列。

若最长上升子序列不止一个，输出最靠前的一个。

输入/输出样例

6
9 3 6 1 2 7

3 6 7

样例解释

最长上升子序列是{3, 6, 7}，长度3。

说明/提示

时间1000ms，内存256MiB