Max Add

时间限制：2s
空间限制：1024MB

题目描述

对长度为 $k$ 的正整数序列 $a$，依次对 $i=1,2,\ldots,k$ 执行：把当前序列中的最大值加到 $a_i$ 上。定义 $f(a)$ 为全部操作结束后的元素总和。

给定长度为 $N$ 的序列 $A$。对每个 $1\le k\le N$，求 $f(A_1,A_2,\ldots,A_k)$。

输入格式

第一行一个整数 $N$。第二行 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

输出 $N$ 行，第 $k$ 行表示长度为 $k$ 的前缀对应的答案。

样例输入 1

3
1 2 3

样例输出 1

2
8
19

数据范围

对于所有数据，$1\le N\le2\times10^5$，$1\le A_i\le10^7$。