K. Monster-Slayer
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Saitama, the One-Punch Man, is on a mission to defeat a group of monsters in order to challenge the monster boss, Centichoro. The power level of each of the $$$i$$$ monsters is stored in an array, where $$$p_i$$$ denotes the power level of the monster at index $$$i.$$$ Saitama's goal is to defeat the most powerful group of monsters by finding the maximum sum of any contiguous subarray of monster strengths. If he does so, he will be able to fight against Centichoro to save humanity. Help Saitama calculate the sum of the power levels of the corresponding subarray!

Note: The subarray of $$$a$$$ is $$$a$$$ contiguous part of the array $$$a$$$, i.e. the array $$$a_i,a_{i+1}...,a_j$$$ for some $$$1 \leq i \leq j \leq n$$$.

Input

The first line contains a single integer, ($$$1 \leq n \leq 10^5$$$), denoting the number of monsters. The following line will contain $$$n$$$ integers denoting the power levels $$$p_i$$$ ($$$-10^9 \leq p_i \leq 10^9$$$) of each of the $$$n$$$ monsters in order.

Output

Output a single integer representing the sum of the power levels in the maximum subarray.

Example
Input
9
-2 10 -3 5 -2 1 2 6 -1
Output
19
Note

In the sample case, the contiguous subarray with the maximum sum is $$$[10, -3, 5, -2, 1, 2, 6]$$$, which has a sum of $$$19$$$. Therefore, Saitama needs to defeat this set of monsters to achieve his goal of challenging Centichoro.