题目描述

对于数组 $a = (a_1, a_2, ..., a_n)$，$f(a)$ 函数定义为进行完以下操作后数组 $a$ 的元素和。

以 i = 1, 2, 3, ..., k 的顺序进行以下操作：

对 $a_i$ 加上当前 $a$ 数组的最大值。

现在给定长度为 N 的数组 $a = (a_1, a_2, ..., a_N)$，分别计算 $a$ 的子数组 $A_i = (a_1, a_2, ..., a_i)$ 的 $f(A_i)$ 的函数值

输入

第一行为 N $(1 \leqslant N \leqslant 10^5)$

第二行有 N 个数，给出数组 $a$ $(1 \leqslant a_i \leqslant 10^9)$

输出

每一行输出一个数 $f(A_i)$

样例

输入：

3
1 2 3

输出：

2
8
19

样例解释

对于 $a$ 的子数组 $A_3$，$f(A_3)$ 的计算过程如下：

s1. 首先对于 i = 1，现在的最大值为 3，则 a1 = 1 + 3，数组变为 A3 = (4, 2, 3)

s2. 然后对于 i = 2，现在的最大值为 4，则 a2 = 2 + 4，数组变为 A3 = (4, 6, 3)

s3. 最后对于 i = 3，现在的最大值为 6，则 a3 = 3 + 6，数组变为 A3 = (4, 6, 9)

最后的 $f(A_3) = 4 + 6 + 9 = 19$