You are given an array. You must apply the following operation until only one element remains.

You need to tell what is the maximum element that can remain. The array can have negative elements.

The operation is:

Choose an element, remove it, combine it's adjacent one's into sum.

For example: 1 2 3 4 5 -> I remove 3rd element -> 1 6 5.

If element is remove from corner, it is just removed, for example from above, I can remove 1 and array will become 2 3 4 5.

The length of array can be upto 10 ^ 5.