题目描述

小 X 正在玩一款 RPG 游戏，他扮演的角色包围了面前的一排 n 个怪物。怪物从左到右排成一排，第 i 只怪物战斗力为 ai。
小 X 有两种技能可以使用：
斩击：该技能可以秒杀其中的一个怪物（被击杀的怪物消失）。在此之后与被击杀怪物相邻的两只怪物会融合成一个新的怪物，融合后的怪物的战斗力是原先两只怪物的战斗力之和。融合后的怪物占据被击杀怪物与相邻的两个怪物的原位置，其它怪物的相对顺序保持不变。当然，如果被击杀的怪物处在最左边或最右边，那么不会有怪物发生融合。斩击技能可无限次使用，每次使用秒杀一个怪物。
驯化：小 X 可以选择一只怪物驯化并据为己有。驯化只能使用一次。
由于小 X 十分的强大，他并不关心怪物对自己造成的伤害，而是好奇他能驯化的怪物的战斗力最大是多少。

输入格式

输入第一行有一个正整数 n，表示怪物的数量。
第二行包含 n 个正整数，表示每只怪物的战斗力。

输出格式

输出一个正整数，表示小 X 可以驯化的怪物的最大战斗力。

样例数据

input1

3
1 2 3

output1

4

说明1

最优操作：
斩击第 2 只怪物（战斗力 2）→ 第 1、3 只怪物融合为 1+3=4
驯化该融合怪物，战斗力为 4。

input2

5
2 2 2 2 2

output2

6

说明2

可以最优的操作：
斩击第 2 只怪物（战斗力 2）→ 第 1、3 只怪物融合为 2+2=4 → 此时怪物数组为 [4, 2, 2]
再斩击第 2 只怪物 → 第 1、3 只怪物融合为 4+2=6
驯化 6。

数据范围与提示

对于 30% 的数据，n 为偶数且第 i 只怪物的战斗力为 i；
对于 100% 的数据，n ≤ 100000，怪物的战斗力为不超过 10⁹ 的正整数。