题目描述

青最近向尘学习了一种序列魔法。对于数列 $a = (a_1, a_2, a_3, \dots, a_k)$，当青向其作用序列魔法后，数列将按以下方式变化：

• 按照 $i = 1, 2, 3, \dots, k$ 的顺序，$a_i$ 将依次加上当前 $a$ 中的最大值。

现在有一个长度为 $N$ 的数列 $A = (A_1, A_2, A_3, \dots, A_N)$。

青想知道，对于每个 $1 \leq k \leq N$，当 $a = (A_1, A_2, A_3, \dots, A_k)$ 时，序列魔法作用后序列的和是什么。

你能帮助他算出结果吗？

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^7$
• 输入中的所有值均为整数

输入格式

输入以如下格式从标准输入中给出。

$N$
$A_1$ $A_2$ $A_3$ $\dots$ $A_N$

输出格式

输出共 $N$ 行。第 $k$ 行输出当 $a = (A_1, A_2, A_3, \dots, A_k)$ 时，序列魔法作用后序列的和。

输入输出样例 #1

输入 #1

3
1 2 3

输出 #1

2
8
19

样例解释 1

例如，当 $a = (A_1, A_2, A_3)$ 时，序列魔法的作用过程如下：

• 首先 $i = 1$，当前 $a$ 的最大值为 $3$，将其加到 $a_1$ 上。此时 $a = (4, 2, 3)$。
• 接着 $i = 2$，当前 $a$ 的最大值为 $4$，将其加到 $a_2$ 上。此时 $a = (4, 6, 3)$。
• 最后 $i = 3$，当前 $a$ 的最大值为 $6$，将其加到 $a_3$ 上。此时 $a = (4, 6, 9)$。
• 最后的 $a$ 的总和为 $19$。