题目分析

给定一个数组，可以进行任意次操作：每次选择两个不同的下标 i 和 j，将 a[i] 修改为 a[i] + a[j]，并将 a[j] 修改为 0。操作的目标是最大化数组的所有前缀最大值之和。

解题思路

1. 观察操作的影响：每次操作实际上是将 a[j] 的值累加到 a[i] 上，并将 a[j] 置零。这意味着我们可以将所有正数集中到一个位置，而其他位置为零。
2. 最大化前缀和：如果所有正数都集中到一个位置（比如第一个位置），那么所有前缀的最大值都会是这个正数的和。此时，前缀最大值之和为 sum_of_positives * n。
3. 特殊情况处理：

题目内容

给定一个由 $n$ 个整数构成的数组 {$a_1,a_2,...,a_n$} ，你可以进行以下操作任意次：

• 选取两个不同的下标 $i,j(1 ≦ i,j≦ n,i≠j)$ ，同时将 $a_i$ 修改为 $a_i+a_j$ ，并将 $a_j$ 修改为 $0$ 。

请你输出在若干次操作后，数组的全部 $n$ 个前缀最大值之和。换句话说，计算下式的答案：

$\sum^n_{i=1}max(a_1,a_2,...,a_i)$

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤ T≤ 10^4)$ 代表数据组数。此后对于每组测试数据：

第一行输入一个整数 $n(1≦n≦2×10^5)$ ，表示数组的长度；

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(-n ≦a_i≦ n)$ ，表示数组的元素。

此外，保证所有测试数据中 $n$ 的总和不超过 $2×10^5$ 。

输出描述

对于每组测试数据，输出一个整数，表示所求的最大值。

样例1

输入

2
3
3 2 -1
1
-1

输出

15
-1

说明

对于第一组数据，其中一种最优选择方案为 $i= 1,j= 2$，操作后数组变为 {$5,0,-1$}，表达式之和即为 $5+max(5,0)+max(5,0,-1)= 15$ 。