题目描述

桌上有 $N$ 颗糖果排成一排。每颗糖果都有一个称为 美味值 的值。从左数第 $i$ 颗糖果的美味值为 $A_i$（$1 \le i \le N$）。

JOI-chan 决定吃掉其中一部分糖果。她希望最大化所吃糖果的美味值总和。

然而，JOI-chan 认为仅贪心地选择糖果并不有趣，因此她制定了一条规则：她不能同时选择两颗相邻的糖果。

JOI-chan 尚未决定要吃多少颗糖果，因此她想知道，对于每个 $j$（$1 \le j \le \lceil \frac{N}{2} \rceil$），当她吃掉 $j$ 颗糖果时，所能获得的最大美味值总和是多少。这里 $\lceil x \rceil$ 表示不小于 $x$ 的最小整数。

任务

给定糖果数量和每颗糖果的美味值，编写一个程序，计算对于每个 $j$（$1 \le j \le \lceil \frac{N}{2} \rceil$），当她吃掉 $j$ 颗糖果时，所能获得的最大美味值总和。

输入格式

从标准输入读取以下数据：

• 输入第一行包含一个整数 $N$。这表示桌上有 $N$ 颗糖果。
• 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含一个整数 $A_i$。这表示从左数第 $i$ 颗糖果的美味值为 $A_i$。

输出格式

向标准输出写入 $\lceil \frac{N}{2} \rceil$ 行。第 $j$ 行（$1 \le j \le \lceil \frac{N}{2} \rceil$）输出当她吃掉 $j$ 颗糖果时所能获得的最大美味值总和。

5
3
5
1
7
6

7
12
10

20
623239331
125587558
908010226
866053126
389255266
859393857
596640443
60521559
11284043
930138174
936349374
810093502
521142682
918991183
743833745
739411636
276010057
577098544
551216812
816623724

936349374
1855340557
2763350783
3622744640
4439368364
5243250666
5982662302
6605901633
7183000177
7309502029

提示

样例 1 解释

在样例输入 1 中，共有 5 颗糖果，从左至右的美味值分别为 3、5、1、7、6。JOI-chan 应按如下方式吃糖果：

• 当她吃 1 颗糖果时，她吃从左数第 4 颗糖果（美味值为 7）。
• 当她吃 2 颗糖果时，她吃从左数第 2 颗和第 4 颗糖果（美味值为 5、7）。
• 当她吃 3 颗糖果时，她吃从左数第 1 颗、第 3 颗和第 5 颗糖果（美味值为 3、1、6）。

再次强调，她不能同时选择两颗相邻的糖果。例如，请记住当她吃 2 颗糖果时，她不能同时吃从左数第 4 颗和第 5 颗糖果（美味值为 7、6）。

数据范围

所有输入数据满足以下条件：

• $1 \le N \le 200\,000$。
• $1 \le A_i \le 1\,000\,000\,000$（$1 \le i \le N$）。

子任务

共有 2 个子任务。每个子任务的得分及附加约束如下：

子任务 1 [8 分]

• $N \le 2\,000$。

子任务 2 [92 分]

无额外约束。

翻译由 Qwen3-235B 完成