暂无测试数据。

题目描述

一个数的序列 \(b_i\)，当 \(b_1<b_2<\cdots<b_S\) 的时候，我们称这个序列是上升的。

对于给定的一个序列 \(\{a_N\}\)，我们可以得到一些上升的子序列 \(\{a_{i_K}\}\)，这里 \(1\le i_1<i_2<\cdots<i_K\le N\)。

比如，对于序列 \(\{1,7,3,5,9,4,8\}\)，有它的一些上升子序列，如 \(\{1,7\}\)，\(\{3,4,8\}\) 等等。

这些子序列中和最大为 \(18\)，为子序列 \(\{1,3,5,9\}\) 的和。

你的任务，就是对于给定的序列，求出最大上升子序列和。

注意，最长的上升子序列的和不一定是最大的，比如序列 \(\{100,1,2,3\}\) 的最大上升子序列和为 \(100\)，而最长上升子序列为\(\{1,2,3\}\)，和仅为 \(6\)。

输入格式

输入的第一行是原序列的长度 \(N\)。

第二行给出原序列中的 \(N\) 个整数，第 \(i\) 个整数为 \(a_i\)。

输出格式

输出一个整数，表示最大上升子序列和。

样例 #1

样例输入 #1

7
1 7 3 5 9 4 8

样例输出 #1

18

提示

【数据范围】

对于 \(20\%\) 的数据，\(N\le20\)。
对于 \(100\%\) 的数据，\(1\le N\le10^3\)。