#1399. 序列分段

序列分段

题目描述

给定长度为 nn 的序列 aa,要求将 aa 分割成恰好 kk 段,每一段内的所有数字都求和,得到一个长度为 kk 的序列 bb。

接着,最大化以下式子的和:

∑i=1ki×bi。\sum\limits_{i=1}^k i\times b_i。

即:b1×1+b2×2+b3×3+...+bk×kb_1\times1+b_2\times 2+b_3 \times3+...+b_k\times k。

更通俗的:

请最大化:“第一段的和乘 11,加上第二段的和乘 22,一直加到第 kk 段的和乘 kk ”。

现在,请你对每一个 k (1≤k≤n)k\ (1 \leq k \leq n),都求出并回答上述式子的最大值吧。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 TT,表示数据组数。

接下来包含 TT 组数据,每组数据的格式如下:

第一行一个正整数 nn,表示序列 aa 的长度。

第二行 nn 个整数 a1,a2,⋯ ,ana_1, a_2, \cdots,a_n,表示序列 aa。

输出格式

对于每组测试数据:

在单独的一行输出由空格分隔的 nn 个整数,其中第 ii 个整数表示:把数组分为 ii 段时,上述式子的最大值。

样例

2
6
1 3 -4 5 -1 -2
1
100
2 4 5 3 1 -2
100

题目来源:洛谷 U552155