题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

如下图所示，从左到右排列着 $N$ 个位置。

从这些位置中选择两个不同的位置，各放置一只蜜蜂；再从剩下的位置中选择一个位置放置蜂巢。如下图所示，浅灰色的位置表示蜜蜂所在位置，深灰色的位置表示蜂巢所在位置。

两只蜜蜂会笔直地朝着蜂巢飞行，并在途中经过的每一个位置采集蜂蜜。每个位置上标注的数字表示蜜蜂经过时可以采集到的蜂蜜数量。

1. 如果两只蜜蜂都经过了某个位置，则它们都会各自采集标注的数量（包括蜂巢所在位置）。
2. 蜜蜂在起始位置不会采蜜。

当按如下图所示进行布置时，两只蜜蜂各自会采到 $4 + 1 + 4 + 9 + 9 = 27$ 的蜂蜜，总共为 $54$。

当按如下图所示进行布置时，从最左侧位置出发的蜜蜂会采到 $9 + 4 + 4 + 9 + 9 = 35$ 的蜂蜜，另一只蜜蜂会采到 $4 + 9 + 9 = 22$ 的蜂蜜，总共为 $57$。

而当按另一种方式布置时，总蜂蜜量为 $31$。

请你编写一个程序，输入每个位置上蜂蜜的数量，计算蜜蜂能够采集到的最大蜂蜜总量。

输入格式

第一行输入一个整数 $N$，表示位置数量。

第二行输入 $N$ 个整数，表示从左到右各个位置的蜂蜜数量，数字之间以空格分隔。

输出格式

输出一个整数，表示蜜蜂能够采集到的最大蜂蜜总量，占据一行。

7
9 9 4 1 4 9 9

57

3
2 5 4

10

提示

约束条件

• $3 \leq N \leq 100\,000$
• 每个位置的蜂蜜数量是 $1$ 到 $10\,000$ 之间的整数

子任务

1. （11 分）$N \leq 20$
2. （13 分）$N \leq 500$
3. （31 分）$N \leq 5\,000$
4. （45 分）无附加约束条件