桌上有一排 $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$ 颗糖果时美味度之和的最大值。
数据范围
所有输入数据满足以下条件：
- $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 分]
无附加限制。
样例
样例输入 1
5 3 5 1 7 6
样例输出 1
7 12 10
说明
在样例 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）。
样例输入 2
20 623239331 125587558 908010226 866053126 389255266 859393857 596640443 60521559 11284043 930138174 936349374 810093502 521142682 918991183 743833745 739411636 276010057 577098544 551216812 816623724
样例输出 2
936349374 1855340557 2763350783 3622744640 4439368364 5243250666 5982662302 6605901633 7183000177 7309502029