题目描述

设有由 $n(1 \le n \le 200)$ 个整数组成的数列：

$b(1), b(2), \ldots, b(n)$。

若存在下标 $i_1 < i_2 < \cdots < i_e$，并且满足：

$b(i_1) \le b(i_2) \le \cdots \le b(i_e)$

则称这些数构成一个长度为 $e$ 的不下降子序列。

请你求出原数列中最长不下降子序列的长度。

例如，数列：

13, 7, 9, 16, 38, 24, 37, 18, 44, 19, 21, 22, 63, 15

其中：

13, 16, 18, 19, 21, 22, 63

是一个长度为 7 的不下降子序列。

同时：

7, 9, 16, 18, 19, 21, 22, 63

是一个长度为 8 的不下降子序列。

因此答案为 8。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数，表示原数列。

输出格式

输出一行，格式为：

Max=最长长度

注意：本题只要求输出最长不下降子序列的长度，不需要输出具体序列。

输入输出样例 #1

输入 #1

14
13 7 9 16 38 24 37 18 44 19 21 22 63 15

输出 #1

Max=8

数据范围与提示

对于全部数据，$1 \le n \le 200$。

可以使用动态规划求解：

令 $dp[i]$ 表示以第 $i$ 个数结尾的最长不下降子序列长度。

如果 $j < i$ 且 $b(j) \le b(i)$，则可以用 $dp[j] + 1$ 更新 $dp[i]$。