An expedition logs n altitude gains at waypoints, in visiting order (values may be negative). A climb is a subsequence of waypoints (not necessarily adjacent), in visiting order, whose values are strictly increasing. First determine the length L of the longest climb. Then, among all climbs of that maximum length L, report the largest possible sum of their values. (You compare sums only among the longest climbs, not against shorter ones.)
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the values in visiting order.
Output format
A single integer: the maximum element sum achievable by a longest strictly increasing subsequence.
Constraints
- 1 <= n <= 2000
- -1000000 <= value <= 1000000
- The answer fits in a signed 64-bit integer.