分数: 700 点
问题陈述
有 N 数轴上的糖果。 i左边第一个糖果位于该位置 2i 并且有味道 a_i。 在这里,可以保证所有糖果的味道都是独一无二的。
Snuke 和 Ant 决定玩一个交替拿一颗糖果的游戏。 游戏开始时,Ant 选择一个位置 1,3,\ldots, 2N+1 站在那里。
Snuke 先行。轮到他时,他可以选择任何一种糖果并获得它。
轮到蚂蚁了,她选择以下两种糖果中味道最好的一种:离她左边最近的糖果和离她右边最近的糖果。如果只有一个方向有糖果,她会选择最近的一个。
当没有剩余糖果时游戏结束。 对于每个职位 1, 3, \ldots, 2N+1,找出当 Ant 选择该位置时 Snuke 所吃到的糖果的味道的最大可能总和。
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 400
- 1 \leq a_i \leq 10^{6}
- a_i 是不同的。
输入
输入由标准输入按以下格式给出:
N a_1 a_2 \ldots a_N
输出
打印 N+1 行。的 i- 第行应包含当 Ant 最初站在该位置时 Snuke 所获取的糖果的味道的最大可能总和 2i-1.
示例输入 1
7 4 3 1 2 1000 2000 3000
示例输出 1
6004 6004 6004 6001 5007 4007 4007 4007
- 我们将解释当 Ant 最初处于该位置时 Snuke 的一种最佳策略 7.
- Snuke选择美味的糖果 1.
- 蚂蚁左边和右边的糖果有以下味道 分别为 3 和 2。她选那个味道最好的,就是那个好吃的 3.
- Snuke选择美味的糖果 1000.
- 蚂蚁左边和右边的糖果有以下味道 分别为 4 和 2。她选那个味道最好的,就是那个好吃的 4.
- Snuke选择美味的糖果 2000.
- 蚂蚁左边没有糖果,蚂蚁右边的糖果有以下味道 2。她选择了这款糖果,味道鲜美 2.
- Snuke选择美味的糖果 3000.
- Snuke 吃过的糖果的味道总和是 6001。没有任何一种方法可以让糖果的整体味道更好。
示例输入 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