奇偶争锋

题号：NC314887
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 有 $n$ 块宝石，每块宝石有一个重量 $a_i$ 。现在将所有重量为”奇数”的宝石分给红队，所有重量为“偶数”的宝石分给蓝队。
$\hspace{15pt}$ 游戏开始前，定义红队的初始累计总重量为红队中最重的那块宝石的重量（如果红队没有宝石，则为 $0$ ），蓝队的初始累计总重量为蓝队中最重的那块宝石的重量（如果蓝队没有宝石，则为 $0$ ）。注意，这些最重的宝石仍然留在各自队伍中，并未移除。

$\hspace{15pt}$ 接下来进行若干轮操作，每轮按序分别进行如下操作：
$\hspace{23pt}\bullet\,$ 红队从蓝队中取出当前最重的一块宝石，将其重量加到红队的累计总重量上，然后将这块宝石移除。
$\hspace{23pt}\bullet\,$ 蓝队从红队中取出当前最重的一块宝石，将其重量加到蓝队的累计总重量上，然后将这块宝石移除。
$\hspace{15pt}$ 若轮到某队行动时，对方队伍已无宝石可供取出，则该队的累计总重量在本轮及之后变为 $0$ （即使之前有累计值，也被清零）。

$\hspace{15pt}$ 一共进行 $n-1$ 轮操作。在游戏开始前（第 $0$ 轮结束后）记录一次双方累计总重量的较大值，此后每轮结束后再记录一次。总共会得到 $n$ 个记录值（可以证明这一点）。请计算出这些记录值。

输入描述:

第一行输入一个整数 ，表示宝石总数。 
第二行输入  个整数 ，表示每块宝石的重量。

输出描述:

在一行上输出  个整数，依次为初始时刻以及每轮结束后的较大值。

示例1

输入

复制

3
2 4 1

输出

复制

4 5 7

说明

在这个样例中，初始：红队（奇数）宝石：，最重 ；蓝队（偶数）宝石：，最重 ；较大值 。
第一轮，红队从蓝队取最重宝石 ，红队累计 ；蓝队从红队取最重宝石 ，蓝队累计 ；较大值 。
第二轮，蓝队还剩宝石 ，红队已无宝石。红队从蓝队取最重宝石 ，红队累计 ；蓝队无宝石可取，蓝队累计置为 ；较大值 。

示例2

输入

复制

4
2 3 3 1

输出

复制

3 5 8 9

备注:

在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。