C. LIS

题目描述

给定一个长度为 $n$ 的序列，从中选出一个子序列（不一定要连续，但是相对位置不能变化）。 例如 1 2 3 的子序列有 "1","2","3","1 2","1 3","2 3","1 2 3"。"3 1" 不是它的子序列。

要求这个子序列的元素是单调递增的，求出最长的满足条件的子序列的长度。

输入格式

第一行一个整数 $n$。 第二行 $n$ 个非负整数，表示序列中的元素。

输出格式

输出一个整数，表示满足条件的最长子序列的长度。

样例

输入1

5
1 4 2 3 3

输出1

3

（样例中的子序列为 1 2 3）

输入2

5
1 2 3 0 5

输出2

4

数据范围与提示

对于 $100\%$ 的数据，$1 \le n \le 1000$，序列中的元素不超过 $1000$。