题目描述

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

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

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

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

输入描述

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

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

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

此外，保证所有测试数据中 $n$ 的总和不超过 $2\times 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$ 。