2840 「JOISC 2018 Day 4」糖

译自 JOISC 2018 Day4 T1「飴 / Candies」

桌子上有 $N$ 块糖排成一排。每块糖都有一个「美味度」，从左数第 $i$ 块糖有一个美味度 $A_i$。

JOI 酱决定吃掉这 $N$ 块糖之中的一些糖，并想最大化她要吃的糖的美味度之和。

然而，JOI 酱认为只是贪心地选糖吃没有意思，所以她制定了以下规则：不能同时吃连续的两块糖。

JOI 酱没有决定她要吃多少块糖，所以 JOI 酱想知道，对于每一个 $j\ (1\le j\le \left\lceil \frac{N}{2} \right\rceil)$，当她吃 $j$ 块糖时获得的美味度之和的最大值是多少。这里 $\lceil x\rceil$ 是大于等于 $x$ 的最小整数。

任务

给出糖果数目和每块糖的美味度，写一个程序计算，对于每一个 $j\ (1\le j\le \left\lceil \frac{N}{2} \right\rceil)$，当她吃 $j$ 块糖时获得的美味度之和的最大值是多少。

从标准输出读入以下数据： - 第一行包含一个正整数 $N$，表示桌子上有 $N$ 块糖； - 接下来 $N$ 行，第 $i$ 行包含一个正整数 $A_i$。表示从左向右数第 $i$ 块糖的美味度为 $A_i$。

输出 $\left\lceil \frac{N}{2} \right\rceil$ 行，第 $j$ 行输出当她吃 $j$ 块糖时获得的美味度之和的最大值。

在样例一中，有 $5$ 块糖，从左往右的每块糖美味度分别为 $3,5,1,7,6$。

JOI 酱应按如下方法吃糖：

• 当她吃 $1$ 块糖时，她应该吃第 $4$ 块（美味度为 $7$）；
• 当她吃 $2$ 块糖时，她应该吃第 $2$ 块和第 $4$ 块（美味度为 $5,7$）；
• 当她吃 $3$ 块糖时，她应该吃第 $1,3,5$ 块（美味度为 $3,1,6$）。

再一次提醒，她不能同时吃连续的两块糖。例如，当她吃两块糖时，她不能同时吃从左往右数第 $4$ 块和第 $5$ 块糖（美味度为 $7,6$）。

对于全部数据，$1\le N\le 2\times 10^5,1\le A_i\le 10^9$。

对于子任务 $1$，$N\le 2\times 10^3$。若通过可以获得 $8$ 分。

对于子任务 $2$，无附加限制。若通过可以获得 $92$ 分。