题目描述

一支登山队正在一条山脊上勘察。山脊上从左到右分布着 $n$ 个候选营地，其中第 $i$ 个营地的海拔为 $a_i$。

为了确保路线安全，并让队伍逐步适应高度，队长决定从这些营地中挑选若干个作为宿营点。挑选时必须遵守以下规则：

• 只能按照山脊从左到右的顺序选择营地，不能回头；
• 可以跳过任意多个营地；
• 后一个被选中的营地海拔必须严格高于前一个。

队长希望尽可能多地设置宿营点。请问最多能设置多少个宿营点？

输入格式

第一行一个整数 $n$，表示候选营地数量。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示每个营地的海拔。

输出格式

输出一个整数，表示最多能设置的宿营点数量。

样例

5
1 2 3 4 5

5

7
200 100 500 400 300 700 800

4

说明/提示

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 10$
• 对于 $40\%$ 的数据，$n \le 100$
• 对于 $100\%$ 的数据，$1 \le n \le 1000$，$1 \le a_i \le 8848$