给我们一个长度为n的数列a：a1,a2,……,an，我们可以将数列a划分为若干个非空的子数列，确保每个子数列至少包含一个元素，每个元素只能在一个数列中，并对这些子数列依次编号为1，2，3，……,k(k为子数列的个数)。

例如：数列[1,−3,7,−6,2,5]可以被划分为 [1]，[−3,7]，[−6,2]，[5]共四个子数列，并将它们依次编号为1，2，3，4。当然，还有其他很多划分方法。

定义数列a的价值为：子数列的编号乘以子序列所有元素之和的和值。即：value=1*sum1+2*sum2+3*sum3+…+i*sumi+…+k*sumk（其中，i为子数列的编号，sumi为第i个子数列中所有元素之和）。

比如，针对上述示例，按照上述划分方法，可以得到该数列的价值为：value=1*1+2*(-3+7)+3*(-6+2)+4*5=1+8+(-12)+20=17。显然，如果我们选择不同的划分方法，则可以得到不同的价值。

请问，对数列a采用最优划分方法可以得到的最大价值是多少？

        第一行一个整数t（1≤t≤1e4）：测试样例数；

        每个测试样例两行：

  第一行一个整数n（3<=n <=1e5）：数列a的长度。

  第二行n个整数：a1,a2,……,an(-1e8<=ai<=1e8): 数列a的n个元素值；

        测试数据确保，所有测试用例的n之和不超过2e5.

对于每个测试样例，输出一行一个整数：按照最优方式对数列a进行划分所能得到的最大价值。

对于第一个测试用例，可以将数列划分为：[1][−3][7][−6][2][5]共六个子数列，价值为：1*1+2*(−3)+3*7+4*(−6)+5*2+6*5=32，我们再也找不到比它更好的划分方法，使得数列的价值更大了。

对于第二个测试用例，可以将数列划分为：[2][9,−5,−3]共两个子数列，价值为：1*2+2*（9-5-3）=4,这已经最大了。

ZXS2023