博弈博弈博弈！

题目描述

有一个正整数序列 $a$，两人进行游戏，规则如下：

• 当序列中只有一个元素时，游戏结束。
• 否则，两人交替操作，每次需要选出 $a$ 中的两个元素 $a_i,a_j(i\ne j)$，将它们删除并插入一个值为 $\lfloor\frac{a_i+a_j}{2}\rfloor\cdot 2$ 的元素。

先手希望使得最终 $a$ 中留下的数最大化，后手希望最小化，两人都按最优策略进行游戏。求对于给定的长为 $n$ 的序列 $a$ 的每个非空前缀，对该前缀进行游戏的结果，即最后留下的数。

输入格式

第一行一个正整数 $n$，表示序列长度。

接下来 $n$ 个正整数，描述序列 $a$。

输出格式

输出一行表示所求的答案。

样例

Input 1

6
6 3 7 2 5 4

Output 1

6 8 16 18 22 26

Input 2

5
7 13 11 19 1

Output 2

7 20 30 48 50

Input 3

3
3 10 11

Output 3

3 12 24

提示说明

Constraints

$a_i\le 10^9$