Maximum Cumulative Elevation Gain

You are given a hiking trail that is divided into n consecutive segments. Each segment has an integer elevation change. A positive number indicates an elevation gain and a negative number indicates an elevation loss. Your task is to determine the maximum cumulative elevation gain over any contiguous sub-segment of the trail.

If all elevation changes are negative, the maximum cumulative elevation gain is considered to be 0. The answer is computed using a variation of Kadane's algorithm.

The formula to calculate the cumulative elevation gain for a sub-segment starting from index i to j can be expressed in \( \texttt{max_gain} = \max_{i \leq j} \left( \sum_{k=i}^{j} \Delta h_k \right) \) where any negative cumulative sum is reset to 0.

inputFormat

The first line of input contains a single integer n (the number of segments). The second line contains n space-separated integers representing the elevation changes of the trail segments.

Example:

6
-1 2 4 -3 5 2

outputFormat

Output a single integer: the maximum cumulative elevation gain for any contiguous sub-segment of the trail.

Example Output:

10

## sample

6
-1 2 4 -3 5 2

10

</p>