题面描述

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

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

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

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

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

样例 #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}$