E: LISum

問題

長さ $N$ の数列 $A$ が与えられる。 数列 $A$ の最長増加部分列のひとつを $B$ とするとき、$\sum B_i$ の最大値を求めよ。

数列 $A$ の最長増加部分列とは、すべての $i < j$ で $A_i < A_j$ を満たす部分列のうち、最長なものを示す。

制約

入力形式

入力は以下の形式で与えられる。

$N$
$A_1 \dots A_N$

出力

数列 $A$ の最長増加部分列のひとつを $B$ とするとき、$\sum B_i$ の最大値を出力せよ。また、末尾に改行も出力せよ。

サンプル

サンプル入力 1

4
6 4 7 8

サンプル出力 1

21

最長増加部分列は $ (6, 7, 8)$ と $(4, 7, 8)$ である。よって最大値は $21$ である。

サンプル入力 2

3
1000 2 3

サンプル出力 2

5

最長増加部分列は $(2,3)$ のみである。

サンプル入力 3

7
17 17 13 4 20 12 15

サンプル出力 3

31

サンプル入力 4

7
19 16 14 9 4 20 2

サンプル出力 4

39