题目描述

对于数列 $a = (a_1, a_2, a_3, \dots, a_k)$，定义 $f(a)$ 为经过以下操作后 $a$ 的所有元素之和。

• 按照 $i = 1, 2, 3, \dots, k$ 的顺序，依次进行如下操作：
  将当前 $a$ 中的最大值加到 $a_i$ 上。

给定一个长度为 $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)$ 时的 $f(a)$。

输入格式

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

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

输出格式

输出共 $N$ 行。第 $k$ 行输出当 $a = (A_1, A_2, A_3, \dots, A_k)$ 时的 $f(a)$。

样例 1

输入

3
1 2 3

输出

2
8
19

说明/提示

限制条件

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

样例解释 1

例如，当 $a = (A_1, A_2, A_3)$ 时，$f(a)$ 的计算过程如下：

• 首先 $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$，这就是 $f(a)$ 的值。

由 ChatGPT 4.1 翻译