制作信箱

题目描述

小童想亲手制作一个木质的信箱，于是他到林中收集木棍，在收集木棍的过程中有一个原则，新收集的木棍要比上一个收集的木棍要长，现有如下木棍，从左到右顺序收集的话，小童最多可以收集多少根木棍。

输入格式

第一行一个整数 $n$，表示木棍的数量。($1 \le n \le 1000$)

第二行有 $n$ 个正整数，用空格隔开，表示木棍的长度。(单根木棍长 $\le 10^9$)

输出格式

一个整数，表示可收集的最大木棍数量。

样例输入 #1

8
22 18 5 11 7 15 20 13

样例输出 #1

4

数据范围

$1 \le n \le 1000$，单根木棍长度不超过 $10^9$。

知识点与难度

本题涉及的知识点（线性DP、最长上升子序列 LIS）从属于 GESP七级，难度等级：⭐⭐⭐。

测试点分布