P12709 [KOI 2021 Round 1] 采蜜

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

如下图所示，从左到右排列着 $N$ 个位置。  从这些位置中选择两个**不同**的位置，各放置一只蜜蜂；再从剩下的位置中选择一个位置放置蜂巢。如下图所示，浅灰色的位置表示蜜蜂所在位置，深灰色的位置表示蜂巢所在位置。  两只蜜蜂会笔直地朝着蜂巢飞行，并在途中经过的每一个位置采集蜂蜜。每个位置上标注的数字表示蜜蜂经过时可以采集到的蜂蜜数量。 1. 如果两只蜜蜂都经过了某个位置，则它们都会各自采集标注的数量（包括蜂巢所在位置）。 2. 蜜蜂在起始位置不会采蜜。 当按如下图所示进行布置时，两只蜜蜂各自会采到 $4 + 1 + 4 + 9 + 9 = 27$ 的蜂蜜，总共为 $54$。  当按如下图所示进行布置时，从最左侧位置出发的蜜蜂会采到 $9 + 4 + 4 + 9 + 9 = 35$ 的蜂蜜，另一只蜜蜂会采到 $4 + 9 + 9 = 22$ 的蜂蜜，总共为 $57$。  而当按另一种方式布置时，总蜂蜜量为 $31$。 请你编写一个程序，输入每个位置上蜂蜜的数量，计算蜜蜂能够采集到的最大蜂蜜总量。

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

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

**约束条件** - $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 分）无附加约束条件