题目描述

给定一个长度为 $N$ 的整数序列。请从中选出若干个数，使它们在原序列中的位置依次递增，并且数值严格递增。

在所有满足条件的子序列中，求元素之和的最大值。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $a_1,a_2,\ldots,a_N$。

输出格式

输出一行一个整数，表示严格上升子序列的最大元素和。

样例

7
1 7 3 5 9 4 8

18

数据范围与提示

• $1 \le N \le 1000$
• $0 \le a_i \le 10000$