最大上升子序列和

最大上升子序列和

暂无测试数据。

题目描述

一个数的序列 bib_i,当 b1<b2<<bSb_1<b_2<\cdots<b_S 的时候,我们称这个序列是上升的。

对于给定的一个序列 {aN}\{a_N\},我们可以得到一些上升的子序列 {aiK}\{a_{i_K}\},这里 1i1<i2<<iKN1\le i_1<i_2<\cdots<i_K\le N

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

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

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

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

输入格式

输入的第一行是原序列的长度 NN

第二行给出原序列中的 NN 个整数,第 ii 个整数为 aia_i

输出格式

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

样例 #1

样例输入 #1

7
1 7 3 5 9 4 8

样例输出 #1

18

提示

【数据范围】

对于 20%20\% 的数据,N20N\le20
对于 100%100\% 的数据,1N1031\le N\le10^3