桌上有 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 解释

在样例输入 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）。

JOISC 2018