#941. Circular Kadane
Think of the list as a circle (the first element comes after the last one). Find the largest sum of a non-empty part made of neighboring elements.
### Input
The first line has n, the second line has n integers separated by spaces.
### Output
A number.
Examples
Input
7 -9 -17 -7 -11 20 -19 -1
Output
20
Input
8 -11 8 -10 -2 -15 -2 19 -18
Output
19
💡 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.