Maximum Sum with Tiles

Place at most three tiles, each covering two adjacent elements of the original array. Tiles cannot overlap or go out of bounds, and you may place none at all. Find the maximum total of the covered elements.

This site uses a standard input/output protocol.

输入格式

The first line contains N, and the second line contains N integers. This site uses 1≤N≤200000 and elements in −10⁹..10⁹.

输出格式

Output a single integer, the answer.

样例 1

输入：

9
2 3 5 2 3 4 6 4 1

输出：

25

样例 2

输入：

5
1 2 3 3 2

输出：

10

样例 3

输入：

2
-1 -2

输出：

0

样例说明

Example 1: cover 3+5, 3+4, 6+4, for a total of 25. Example 2: cover 2+3 and 3+2, for a total of 10, needing only two tiles. Example 3: all numbers are negative, so placing no tile gives 0.