Predicting the Maximum Gold Medal Interval

Loidc possesses an extraordinary ability to foresee the future, accurately predicting the number of gold medals the Chinese team will win in each unit of time. However, due to the strenuous effort and high workload required to predict these values, he finds it challenging to determine which contiguous time interval results in the maximum total gold medals.

Your task is to help loidc by identifying the contiguous subarray with the maximum sum. Formally, given an array \(a_1, a_2, \dots, a_n\) representing the predicted gold medals for each unit time, you are to compute the value of

$$ \max_{1 \le i \le j \le n} \sum_{k=i}^{j} a_k $$

If all the numbers are negative, output the maximum (i.e. the least negative) among them.

inputFormat

The first line contains an integer (n) ((1 \le n \le 10^5)), denoting the number of unit times. The second line contains (n) space-separated integers (a_1, a_2, \dots, a_n), where each (a_i) represents the predicted gold medals in the (i)-th unit time ((|a_i| \le 10^9)).

outputFormat

Print a single integer representing the maximum sum of any contiguous subarray.

sample

5
1 2 3 -2 5

9