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 翻译