数轴上有 $n$ 颗糖，第 $i$ 颗糖在坐标 $2i$ 处，且有一个美味度 $a_i$ ，保证所有糖果的美味度均不相同。

梦梦和熊熊准备玩一个轮流取一颗糖果的游戏。游戏开始时，熊熊会选择 $1,3,\cdots,2n+1$ 中的一个位置作为初始位置。

梦梦先取糖果，他可以任意取走数轴上还在的任何一颗糖果。

熊熊行动时，它会从离它两边最近的至多两颗糖果中，选择美味度更大的一颗。

当最后没有糖果可取后，游戏结束。对熊熊的每个开始位置 $1,3,\cdots,2n+1$ ，求出梦梦可以获得的糖果的美味度之和的最大值。

输入格式

第一行给定正整数 $n$。

第二行给出长度为 $n$ 的序列 $a$。

输出格式

输出 $n$ 行，每行 $1$ 个整数，表示答案。

7
4 3 1 2 1000 2000 3000

6004
6004
6004
6001
5007
4007
4007
4007

1
1

1
1

2
1 999998

999998
999998
999998

说明与提示

样例解释

以初始位置为 $1$ 为例，梦梦先选择 $4$，熊熊取 $3$，梦梦选 $1000$，熊熊选 $3$，梦梦选 $2000$，熊熊选 $1$，梦梦选$3000$，熊熊选 $2$。

数据范围

对于 $30\%$ 的数据，$1 \leq n \leq 20$。

对于 $100\%$ 的数据，$1 \leq n \leq 400,1 \leq a_i \leq 10^6$