AT_keyence2021_e Greedy Ant

在数轴上有 $N$ 个糖果。从左到右，第 $i$ 个糖果位于位置 $2i$，其美味度为 $a_i$。这里保证所有糖果的美味度互不相同。 すぬけ君和“蟻”轮流取糖果。开始时，“蟻”会选择一个位置 $1,3,\ldots,2N+1$ 中的某一个站立，并开始取糖果。 すぬけ君先手。在自己的回合，すぬけ君可以任选一个糖果取走。 “蟻”在自己的回合时，会从自己当前位置出发，分别向左和向右寻找最近的糖果，然后从这两个糖果中选择美味度较高的那个取走。如果某一方向没有糖果，则取该方向最近的糖果。 当所有糖果都被取完时，游戏结束。请对于“蟻”初始站在 $1,3,\ldots,2N+1$ 的每一种情况，求出すぬけ君能够取得的糖果美味度总和的最大可能值。

输入通过标准输入给出，格式如下： > $N$ $a_1$ $a_2$ $\ldots$ $a_N$

输出共 $N+1$ 行。第 $i$ 行输出当“蟻”初始站在位置 $2i-1$ 时，すぬけ君能够取得的糖果美味度总和的最大可能值。

### 限制条件 - 所有输入均为整数。 - $1 \leq N \leq 400$ - $1 \leq a_i \leq 10^6$ - $a_i$ 互不相同。 ### 样例解释 1 以“蟻”初始站在位置 $7$ 为例，すぬけ君的最优策略如下： - すぬけ君取走美味度为 $1$ 的糖果。 - “蟻”左侧最近的糖果美味度为 $3$，右侧最近的糖果美味度为 $2$，因此“蟻”取走美味度较高的 $3$。 - すぬけ君取走美味度为 $1000$ 的糖果。 - “蟻”左侧最近的糖果美味度为 $4$，右侧最近的糖果美味度为 $2$，因此“蟻”取走美味度较高的 $4$。 - すぬけ君取走美味度为 $2000$ 的糖果。 - “蟻”左侧没有糖果，右侧最近的糖果美味度为 $2$，因此“蟻”取走美味度为 $2$ 的糖果。 - すぬけ君取走美味度为 $3000$ 的糖果。 すぬけ君取得的糖果美味度总和为 $6001$。不存在比这更优的取得方式。 由 ChatGPT 4.1 翻译