Calculate Warehouse Efficiency (Probably for Supply Chain related NG positions --Fungible-- :)

Each day, first pick one package that is still in the warehouse and has not been picked before, adding its weight to the efficiency; then ship out the current leftmost and rightmost packages (only one shipment when a single package remains), until the warehouse is empty. Maximize the total efficiency.

输入格式

The first line contains n (1..200000), and the second line contains n weights (0..10⁹).

输出格式

Output a single integer answer.

样例 1

输入：

6
4 4 8 5 3 2

输出：

17

样例 2

输入：

7
2 1 8 5 6 2 4

输出：

23

样例 3

输入：

1
9

输出：

9

样例说明

Example 1: over three days pick 4, 5, 8 in order, for a total of 17. Example 2: over four days you can pick 4, 6, 8, 5, for a total of 23. Example 3: on the only day pick 9, for a total of 9.