题目描述

小 X 决定建立一个团队，但是现在团队里只有小 X 一个人。

在接下的 $n$ 天里，小 X 每天都会招募到一个人，其中加入的第 $i$ 个人的能力值为 $v_i$，小 X 的能力值为 $v_0=10^{10^{100}}$。

为了更好管理整个团队，小 X 需要将团队分成小组。具体的，假设现在已经有 $k$ 个人加入了团队，小 X 希望找到一个序列 $0=a_0<a_1<\dots <a_m=k+1$，使得对于所有 $0\le i<m-1$，有 $\sum\limits_{j=a_i}^{a_{i+1}-1}v_j>\sum\limits_{j=a_{i+1}}^{a_{i+2}-1}v_j$。

为了让新加入的队员们感受到幸福感，小 X 希望 $a_m$ 尽可能大，在此基础上 $a_{m-1}$ 尽可能大，在此基础上 $a_{m-2}$ 尽可能大，以此类推。换句话说，让序列 $a_m,a_{m-1},a_{m-2}\dots a_1$ 的字典序尽可能大。

但是小 X 现在正忙于招募队员，所以他希望你来帮他解决这一问题，你只需要告诉他在 $k=1,2\dots n$ 的时候， $\sum\limits_{i=0}^m(i\times a_i)$ 的值即可。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数，其中第 $i$ 个数为 $v_i$。

输出格式

输出仅一行，包含 $n$ 个以空格隔开的整数，其中第 $i$ 个数表示 $k=i$ 时的答案。

5
1 3 3 2 4

5 8 19 39 31

提示

【样例 1 解释】

• 对于 $k=1$，有 $m=2$，$a_0=0,a_1=1,a_2=2$，输出 $0\times 0+1\times 1+2\times 2=5$。
• 对于 $k=2$，有 $m=2$，$a_0=0,a_1=2,a_2=3$，输出 $0\times 0+1\times 2+2\times 3=8$。
• 对于 $k=3$，有 $m=3$，$a_0=0,a_1=1,a_2=3,a_3=4$，输出 $0\times 0+1\times 1+2\times 3+3\times 4=19$。
• 对于 $k=4$，有 $m=4$，$a_0=0,a_1=1,a_2=3,a_3=4,a_4=5$，输出 $0\times 0+1\times 1+2\times 3+3\times 4+4\times 5=39$。
• 对于 $k=5$，有 $m=3$，$a_0=0,a_1=3,a_2=5,a_3=6$，输出 $0\times 0+1\times 3+2\times 5+3\times 6=31$。

【样例 2】

见选手目录下的 divide/divide2.in 与 divide/divide2.ans。

样例 $2$ 满足测试点 $1\sim 3$ 的限制。

【样例 3】

见选手目录下的 divide/divide3.in 与 divide/divide3.ans。

样例 $3$ 满足测试点 $4\sim 6$ 的限制。

【样例 4】

见选手目录下的 divide/divide4.in 与 divide/divide4.ans。

样例 $4$ 满足测试点 $7\sim 10$ 的限制。

【样例 5】

见选手目录下的 divide/divide5.in 与 divide/divide5.ans。

样例 $5$ 满足测试点 $13\sim 15$ 的限制。

【子任务】

对于全部的测试数据，保证 $1\le n\le 10^5$，$1\le v_i\le n$。

测试点	$n \le$	特殊性质
$1\sim 3$	$10$	无
$4\sim 6$	$100$
$7\sim 10$	$5000$
$11,12$	$5\times 10^4$
$13\sim 15$	$10^5$	$v_i$ 随机生成
$16\sim 20$		无