题目描述

给定一个长度为N的整数序列，求所有非空严格上升子序列中，元素和的最大值。

子序列不要求连续，但必须保持原顺序。注意：长度最长的上升子序列不一定具有最大的元素和。

输入格式

第一行整数N。第二行N个整数。

输出格式

输出严格上升子序列的最大元素和。

样例

7
1 7 3 5 9 4 8

18

数据范围

1≤N≤1000；每个整数在0至10000之间，可以重复。