题目描述

给你一个序列 a1, a2, …, an，这个序列会有很多上升子序列。你要求出所有上升子序列中，和最大的一个，输出最大的和。

（只有一个数的子序列，也认为是上升子序列）

输入格式

第 1 行，一个正整数 n。

第 2 行，n 个正整数 a1, a2, …, an。

输出格式

一个整数，最大的上升子序列和。

输入样例 #1

6
8 1 2 3 9 4

输出样例 #1

17

输入样例 #2

1
606863184

输出样例 #2

606863184

输入样例 #3

2
403329628 198535183

输出样例 #3

403329628

数据范围与约定

1 ≤ n ≤ 1000。

1 ≤ ai ≤ 10^9。