背景

“不要贪恋过去，也不要忧患未来，没有任何的意义，我们唯一能做的是活在当下，当下也是我们唯一能够抓住的”

题目描述

excuse在睡觉前很容易对问题产生执念，并且经常因此做噩梦。为了解决他的执念，他去看了医生 小医仙。

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

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

这种划分的 OVO 值定义为 $\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$。

excuse想知道，对于任意一种划分方式， OVO 值的最大值是多少。

$^{\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$ 的最大 OVO 值。

输入输出样例 #1

输入 #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

说明/提示

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

限制

1s,256MiB.