1995: 最小的LIS

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

给定N个元素的序列S₁, S₂, S₃, ... , S_N，它的子序列可认为是原序列的一个子集。如果子序列中的元素满足对每个i<j，都有S_i<S_j，则它就是一个原序列的上升子序列。LIS问题，即在所有的上升子序列中，寻找项数最多的子序列。

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

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

输入包含N个整数S₁, S₂, S₃, ... , S_N，用空格隔开。

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

1 2 3 2 5 6 0

1 2 3 5 6