最大和上升子序列

题目描述

给定一个长度为 $n$ 的数组 $a_1,a_2,\dots ,a_n$，问其中的和最大的上升子序列。也就是说，我们要找到数组 $p_1,p_2,\dots,p_m$，满足 $1\leq p_1 < p_2 < \dots < p_m \leq n$ 并且 $a_{p_1} < a_{p_2} < \dots < a_{p_m}$，使得$a_{p_1} + a_{p_2} + \dots + a_{p_m}$最大。

输入格式

第一行一个数字 $n$。

接下来一行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

一个数，表示答案。

样例输入

6
3 7 4 2 6 8

样例输出

21

数据范围

所有数据保证 $1\leq n\leq 1000, 1 \leq a_i \leq 10^5$。