P83088

最长上升子序列2

题目描述

有n个数，找出最长的上升子序列（Longest Increasing Subsequence），并求LIS的长度。

输入

第一行为一个正整数n。 第二行为n个整数。

输出

最长上升子序列的长度。

样例

样例 1

输入

6
4 2 4 5 3 7

输出

4

提示

此题意与2005相同，但要求测试更大的数据。

对30%的数据，1\le n\le 10000。

对100%的数据，1\le n\le 10^6。

来源

动规专题