#903. Maximum subarray sum
Find the largest sum of a non-empty part of the list made of neighboring elements (Kadane).
### Input
The first line has n, the second line has n integers separated by spaces.
### Output
A number.
Examples
Input
9 -12 -4 -5 -10 -19 -3 -5 -18 3
Output
3
Input
10 3 -2 -18 -12 19 -1 1 2 17 10
Output
48
💡 You can solve it with Python, JavaScript or blocks. Read the input line by line with input(). Don't print a question (like input("Number: ")). Print exactly what the output asks for, nothing more.