A drone samples n signed skyline offsets across a city, in scan order (values may be negative). A peak profile is a subsequence of samples (not necessarily adjacent), in scan order, whose values strictly increase to a single peak sample and then strictly decrease. A purely strictly-increasing subsequence and a purely strictly-decreasing subsequence both qualify, and a single sample is a peak profile by itself. Among all peak profiles, report the maximum possible sum of the chosen values (the profile must be non-empty).
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the offsets in scan order.
Output format
A single integer: the maximum element sum of a bitonic subsequence.
Constraints
- 1 <= n <= 2000
- -1000000 <= offset <= 1000000
- The answer fits in a signed 64-bit integer.