CF1903C Theofanis' Nightmare

Theofanis 在睡觉前很容易对问题产生执念，并且经常因此做噩梦。为了解决他的执念，他去看了医生 Dr. Emix。 在他最近的噩梦中，他有一个长度为 $n$ 的数组 $a$，他想要将其划分为若干个非空子数组 $^{\dagger}$，使得每个元素恰好属于一个子数组。 例如，数组 $[1,-3,7,-6,2,5]$ 可以被划分为 $[1]\,[-3,7]\,[-6,2]\,[5]$。 这种划分的 Cypriot 值定义为 $\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i$，其中 $k$ 是划分得到的子数组个数，$\mathrm{sum}_i$ 表示第 $i$ 个子数组的元素和。 例如，上述划分 $[1]\,[-3,7]\,[-6,2]\,[5]$ 的 Cypriot 值为 $1 \cdot 1 + 2 \cdot (-3 + 7) + 3 \cdot (-6 + 2) + 4 \cdot 5 = 17$。 Theofanis 想知道，对于任意一种划分方式，Cypriot 值的最大值是多少。 $^{\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 \times 10^5$。

对于每个测试用例，输出一个整数，表示数组 $a$ 的最大 Cypriot 值。

在第一个测试用例中，为了获得最大 Cypriot 值，我们将数组划分为 $[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$。 由 ChatGPT 4.1 翻译