CF1903C.Theofanis' Nightmare

Theofanis easily gets obsessed with problems before going to sleep and often has nightmares about them. To deal with his obsession he visited his doctor, Dr. Emix.

In his latest nightmare, he has an array $a$ of size $n$ and wants to divide it into non-empty subarrays$^{\dagger}$ such that every element is in exactly one of the subarrays.

For example, the array $[1,-3,7,-6,2,5]$ can be divided to $[1] [-3,7] [-6,2] [5]$.

The Cypriot value of such division is equal to $\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i$ where $k$ is the number of subarrays that we divided the array into and $\mathrm{sum}_i$ is the sum of the $i$-th subarray.

The Cypriot value of this division of the array $[1] [-3,7] [-6,2] [5] = 1 \cdot 1 + 2 \cdot (-3 + 7) + 3 \cdot (-6 + 2) + 4 \cdot 5 = 17$.

Theofanis is wondering what is the maximum Cypriot value of any division of the array.

$^{\dagger}$ An array $b$ is a subarray of an array $a$ if $b$ can be obtained from $a$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

西奥法尼斯在睡觉前很容易对问题着迷，常常因此做噩梦。为了应对这种痴迷，他去看了他的医生——埃米克斯博士。

在他最近的一场噩梦中，他拥有一个长度为 $n$ 的数组 $a$，并希望将其划分为若干非空子数组$^{\dagger}$，使得每个元素恰好属于其中一个子数组。

例如，数组 $[1,-3,7,-6,2,5]$ 可被划分为 $[1]\ [-3,7]\ [-6,2]\ [5]$。

该划分的**塞浦路斯值（Cypriot value）**定义为 $\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$。

西奥法尼斯想知道：该数组所有可能划分方式中，最大的塞浦路斯值是多少？

$^{\dagger}$ 若数组 $b$ 可通过对数组 $a$ 删除开头若干（可能为零或全部）元素及结尾若干（可能为零或全部）元素而得到，则称 $b$ 是 $a$ 的一个子数组。特别地，任意数组是其自身的子数组。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of two lines.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^{5}$) — the size of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^8 \le a_i \le 10^{8}$) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^{5}$.

第一行包含一个整数 $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}$。

For each test case, print one integer — the maximum Cypriot value of the array $a$.

对于每个测试用例，输出一个整数——数组 $a$ 的最大塞浦路斯值。

In the first test case, to get the maximum Cypriot value we divide the array into $[1][-3][7][-6][2][5]$ which gives us: $\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$

Similarly, in the second test case we divide the array into $[2][9,-5,-3]$ which gives us $\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i = 1 \cdot 2 + 2 \cdot (9 + (-5) + (-3)) = 4$.

在第一个测试用例中，为获得最大的塞浦路斯值，我们将数组划分为 $[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$。