← 返回题目列表

Codeforces · 1903/C

C. 塞奥法尼斯的噩梦

中文机器翻译题面 查看原题

Theofanis 很容易在入睡前沉迷于问题,并且经常做噩梦。为了解决他的困扰,他拜访了他的医生埃米克斯博士。

在他最近的噩梦中,他有一个大小为 $$$n$$$ 的数组 $$$a$$$,并希望将其划分为非空子数组$$$^{\dagger}$$$,以便每个元素都恰好位于其中一个子数组中。

例如,数组 $$$[1,-3,7,-6,2,5]$$$ 可以分为 $$$[1] [-3,7] [-6,2] [5]$$$。

这种除法的塞浦路斯值等于 $$$\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i$$$,其中 $$$k$$$ 是我们将数组划分为的子数组的数量,而 $$$\mathrm{sum}_i$$$ 是第 $$$i$$$ 个子数组的总和。

数组 $$$[1] [-3,7] [-6,2] [5] = 1 \cdot 1 + 2 \cdot (-3 + 7) + 3 \cdot (-6 + 2) + 4 \cdot 5 = 17$$$ 的塞浦路斯值。

Theofanis 想知道数组的任何划分的最大塞浦路斯值是多少。

$$$^{\dagger}$$$ 数组 $$$b$$$ 是数组 $$$a$$$ 的子数组,如果 $$$b$$$ 可以通过删除开头的几个(可能是零个或全部)元素和末尾的几个(可能是零个或全部)元素从 $$$a$$$ 获得。特别是,数组是其自身的子数组。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由两行组成。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^{5}$$$) — 数组的大小。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^8 \le a_i \le 10^{8}$$$) — 数组的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^{5}$$$。

输出

对于每个测试用例,打印一个整数 - 数组 $$$a$$$ 的最大塞浦路斯值。

示例

输入 #1

4
6
1 -3 7 -6 2 5
4
2 9 -5 -3
8
-3 -4 2 -5 1 10 17 23
1
830

输出 #1

32
4
343
830

注意

在第一个测试用例中,为了获得最大塞浦路斯值,我们将数组分为 $$$[1][-3][7][-6][2][5]$$$,这给出了: $$$\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i = 1 \cdot 1 + 2 \cdot (-3) + 3 \cdot 7 + 4 \cdot (-6) + 5 \cdot 2 + 6 \cdot 5 = 32$$$

类似地,在第二个测试用例中,我们将数组分为 $$$[2][9,-5,-3]$$$,这给出了 $$$\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i = 1 \cdot 2 + 2 \cdot (9 + (-5) + (-3)) = 4$$$。