问题描述

LIS (longest increasing subsequence，即最长上升子序列)问题是计算机科学中的一个经典问题。

它的定义是： 给定N个元素的序列S1, S2, S3, ... , SN，它的子序列可认为是原序列的一个子集。如果子序列中的元素满足对每个i<j，都有Si<Sj，则它就是一个原序列的上升子序列。LIS问题，即在所有的上升子序列中，寻找项数最多的子序列。

根据以上定义，LIS问题的解并非唯一的。然而，这里要求输出的是，所有最长上升子序列中字典序最小的一个，这保证了输出的唯一性。

（友情提示：字典序的定义是指，对于两个序列u1, u2, u3, ... , un以及v1, v2, v3, ... , vn，首先比较u1与v1，若u1与v1不相等，则根据u1与v1的大小决定两个序列的字典序大小；若u1与v1相等，再比较u2与v2；若u2与v2不相等，则根据u2与v2的大小决定两个序列的字典序大小；若u2与v2相等，再比较u3与v3……只要两个序列并非完全相同，按照这样的方法总可以比较出它们的字典序大小。）

输入格式

输入包含N个整数S1, S2, S3, ... , SN，用空格隔开。

输出格式

在一行内字典序最小的LIS，两两数字之间用单个空格隔开。

样例输入

1 2 3 2 5 6 0

样例输出

1 2 3 5 6

数据范围

对于40%的数据，N<=1000。

对于100%的数据，N<=50000。

序列中的数在 [-1e9, 1e9] 范围内。