题目描述

在数轴上有 $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

输入 #1

7
4 3 1 2 1000 2000 3000

输出 #1

6004
6004
6004
6001
5007
4007
4007
4007

输入输出样例 #2

输入 #2

40
45651 92206 55173 24815 34809 73343 60978 57984 6919 89624 19693 30037 87070 6713 65976 37597 51929 93304 70911 7343 65414 38977 47998 52123 53590 35714 59319 50872 53850 40991 85668 8808 32846 70831 3416 42173 89538 73410 21502 69631

输出 #2

1416699
1416699
1416699
1416699
1413888
1410894
1410894
1410894
1413888
1413888
1413888
1413888
1413888
1413888
1419943
1419943
1419943
1400961
1400961
1400961
1419943
1419943
1419943
1419749
1419749
1419749
1419749
1419749
1419749
1419749
1419749
1419749
1419943
1419943
1419943
1419943
1398462
1398462
1398462
1402241
1402241

说明/提示

限制条件

• 所有输入均为整数。
• $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$。不存在比这更优的取得方式。