Xiao Ming is a thief with obsessive-compulsive disorder , He has excellent theft skills and is successful repeatedly . Xiao Ming is afraid of spending the rest of his life in prison , He's going to stop after this job .
There are n A house , The wealth value of each house is a[i], Xiao Ming hopes to be here n Steal as much value as possible from a house . Because some houses are in disrepair and other problems, Xiao Ming is at risk of injury when entering the house , So the value of wealth may be negative . Because Xiao Ming has obsessive-compulsive disorder , Every time he makes a move, he will only steal any continuous house , Xiao Ming chooses at least one house to steal .
Input format :
The first line is an integer n(1≤n≤1000000);
The second line n An integer represents the wealth value of each house ai.
Output format :
An integer in a row represents the maximum value Xiao Ming can steal .
sample input :
Here's a set of inputs . for example ：
5
3 4 -1 4 -10
sample output :
Here is the corresponding output . for example ：
10
Sample explanation
Xiao Ming steals 1-4 House No , Value is 3+4+(-1)+4=10
