Maximize the Array Value

Each operation deletes one element: if it is at an end, it is simply deleted; if it is in the middle, it is deleted and its left and right neighbors are merged into their sum. Exactly one element must remain at the end; maximize the final value.

输入格式

The first line contains n, and the second line contains n integers. The original n≤100000 and −10^9≤a[i]≤10^9 are kept; this site specifies n≥1, and the final result cannot be an empty array.

输出格式

Output a single integer answer.

样例 1

输入：

3
-5 -2 -7

输出：

-2

样例 2

输入：

3
1 -10 3

输出：

4

样例 3

输入：

3
0 -1 0

输出：

0

样例说明

The outputs of the three public examples are, in order: -2; 4; 0. Verified by independent enumeration or direct simulation.