题目描述

小Z要将一个长度为 $n$ 的序列分为连续的 $k$ 段，然后将每一段分别求和为 $b_i$，他想最大化

更通俗的：

请最大化：“第一段的和乘 $1$ ，加上第二段的和乘 $2$，一直加到第 $i$ 段的和乘 $i$ ”...

小Z想知道对于每一个 $k\in[1,n]$ 的最后结果

输入格式

第一行，一个正整数 $n$，表示原序列元素个数

第二行，$n$ 个整数 $a_i$

输出格式

$n$ 个数字，表示要分为 $k=i$ 段时最后最大结果

输入输出样例

6
1 3 -4 5 -1 -2

2 4 5 3 1 -2

样例 $\tt \#1$说明

当 $k=3$ 时，分为：

$[1], [3, -4], [5, -1, -2]$

结果最大为 $1\times1+2\times(-1)+3\times2=5$

数据范围

$30\%:n\le 15$

$60\%:n\le 200$

$100\%:n\le 2\times10^5, -10^6\le a_i\le 10^6$