题目描述

芯芯在一片神奇的花园中玩耍。花园里排着一列花朵，每朵花都有一个独特的高度。芯芯很喜欢按照从矮到高的顺序采摘花朵，但她又不想折断任何花，所以：

• 她只能沿着花朵排列的顺序，从左到右的顺序选择性的采摘。
• 每次采摘新的花朵时，高度必须比之前采摘的那朵高。
• 芯芯希望自己能采摘尽可能多的花。

请你帮助芯芯，计算她最多可以按照从矮到高的规则采摘多少朵花。

输入格式

• 第一行包含一个整数 $n$，表示花朵的数量。$(1 \leq n \leq 5000)$
• 第二行包含 $n$ 个整数，第 $i$ 个整数 $h_i$ 表示第 $i$ 朵花的高度。$(1 \leq h_i \leq 1000)$

输出格式

• 输出一个整数，表示芯芯最多可以采摘的花朵数量。

9
8 5 2 8 6 3 6 9 7

4