修行日志中的上升天数

题目描述

在一座云雾缭绕的山门中，弟子阿青坚持把自己的每日修行状态记录成一个整数序列，第 $i$ 天的修行成果记为一个整数 $a_i$。

现在她想从中挑出若干天，组成一份“最顺利的修行日志”。在这份日志中，记录的天数必须按照实际发生的先后顺序排列，并且后一天的成果值一定要严格大于前一天，也就是说，如果选择了若干天 $i_1<i_2<\dots<i_k$，那么需要满足

$$a_{i_1} < a_{i_2} < \dots < a_{i_k}.$$

阿青希望这份日志尽可能长，请你帮她计算：在给定的修行记录中，她最多能选出多少天，组成这样一份严格上升的修行日志。

输入格式

输入共两行。

• 第一行包含一个整数 $n$，表示记录的天数。
• 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，依次表示每一天的修行成果值，整数之间用一个空格分隔。

输出格式

输出一行，一个整数，表示阿青最多能选出的天数。

输入输出样例 #1

输入 #1

6
3 1 4 1 5 9

输出 #1

4

样例解释 #1

一种可行的选择方式是取第 $1,3,5,6$ 天，对应的成果值为 $3,4,5,9$，是一个严格上升的序列，长度为 $4$。可以证明不存在更长的选择方式。

输入输出样例 #2

输入 #2

5
5 4 3 2 1

输出 #2

1

样例解释 #2

由于每一天的成果值都不比前一天大，只能选择任意单独一天，答案为 $1$。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 2000$；
• 对于所有 $1 \le i \le n$，有 $1 \le a_i \le 10^9$。