题目描述

译自 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

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\le N\le 2\times 10^5,1\le A_i\le 10^9$。

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

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