A royalty ledger lists n payout amounts in chronological order. You want to select a subsequence of payouts (not necessarily adjacent), keeping them in chronological order, whose amounts are strictly increasing, so as to maximize the total selected amount. The selected subsequence must be non-empty (a single payout is allowed). Amounts may be negative. Report the maximum achievable total.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the payout amounts in chronological order.
Output format
A single integer: the maximum sum of a strictly increasing subsequence.
Constraints
- 1 <= n <= 1000
- -1000000 <= amount <= 1000000
- The answer fits in a signed 64-bit integer.