Problem Description

To operate a social game, it is essential to observe the daily fluctuations in the number of users.

Punch-kun, who runs a game company, is trying to find out how many users increased during the period when the number of users increased the most.

Given the daily changes in the number of users \( a_1, a_2, \ldots, a_N \), please determine the maximum change in the number of users during any period.

Input Format

The input is given from the standard input in the following format:

\( N \) \( a_1 \) \( a_2 \) ... \( a_N \)

• The first line contains the number of days in the period to be investigated \( N \) \( (1 \leq N \leq 100000) \).
• The second line contains the change in the number of users on the \( i \)-th day \( a_i \) \( (-1000 \leq a_i \leq 1000) \).

Output Format

Output the maximum change in the number of users during any period (of at least one day) in one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

7
3 -4 2 3 -1 2 -1

Sample Output #1

6

Sample Input #2

3
10 20 30

Sample Output #2

60

Sample Input #3

3
-4 -2 -5

Sample Output #3

-2

Notes/Hints

Partial Points

If you correctly solve the test cases where \( 1 \leq N \leq 3000 \), you will be awarded 40 points as partial credit.

Sample Explanation 1

The increase from day 3 to day 6, \( (2, 3, -1, 2) \), is the maximum with a total increase of 6.

Sample Explanation 2

The entire period has the maximum change in the number of users.

Sample Explanation 3

The output can be negative. Note that the period for which the output is calculated must be at least one day.

见题面 Input 部分

见题面 Output 部分