该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给定一长度为n的数列，数列中的每个数都在1～100000之间

请在不改变原数列顺序的前提下，从中取出一定数量的整数（不需要连续），并使这些整数构成单调上升序列。

输出这类单调上升序列的最大长度。

Input Format

输入包括两行，第一行为n，代表数列的长度。（1 ≤ n ≤ 100000）

第二行为n个整数。

Output Format

输出这类单调上升序列的最大长度

5
3 1 5 4 6​

3​

Hint

对于样例的解释：356，156，146 均可组成长度为3的上升子序列

Source

动态规划 基础百练