310874: CF1903C. Theofanis' Nightmare

C. Theofanis' Nightmaretime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Theofanis easily gets obsessed with problems before going to sleep and often has nightmares about them. To deal with his obsession he visited his doctor, Dr. Emix.

In his latest nightmare, he has an array $a$ of size $n$ and wants to divide it into non-empty subarrays$^{\dagger}$ such that every element is in exactly one of the subarrays.

For example, the array $[1,-3,7,-6,2,5]$ can be divided to $[1] [-3,7] [-6,2] [5]$.

The Cypriot value of such division is equal to $\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i$ where $k$ is the number of subarrays that we divided the array into and $\mathrm{sum}_i$ is the sum of the $i$-th subarray.

The Cypriot value of this division of the array $[1] [-3,7] [-6,2] [5] = 1 \cdot 1 + 2 \cdot (-3 + 7) + 3 \cdot (-6 + 2) + 4 \cdot 5 = 17$.

Theofanis is wondering what is the maximum Cypriot value of any division of the array.

$^{\dagger}$ An array $b$ is a subarray of an array $a$ if $b$ can be obtained from $a$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of two lines.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^{5}$) — the size of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^8 \le a_i \le 10^{8}$) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^{5}$.

Output

For each test case, print one integer — the maximum Cypriot value of the array $a$.

ExampleInput

4
6
1 -3 7 -6 2 5
4
2 9 -5 -3
8
-3 -4 2 -5 1 10 17 23
1
830

Output

32
4
343
830

Note

In the first test case, to get the maximum Cypriot value we divide the array into $[1][-3][7][-6][2][5]$ which gives us: $\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$

Similarly, in the second test case we divide the array into $[2][9,-5,-3]$ which gives us $\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i = 1 \cdot 2 + 2 \cdot (9 + (-5) + (-3)) = 4$.

题目大意：
Theofanis在睡前容易对问题过于着迷，并且经常做噩梦。为了解决他的困扰，他去看医生Dr. Emix。在他的最新噩梦中，他有一个大小为n的数组a，并希望将其划分为非空子数组，使得每个元素恰好位于一个子数组中。例如，数组[1,-3,7,-6,2,5]可以划分为[1],[-3,7],[-6,2],[5]。这种划分的塞浦路斯价值（Cypriot value）等于Σ(i=1 to k) i * sum_i，其中k是我们将数组划分成的子数组的数量，sum_i是第i个子数组的和。例如，上述划分的塞浦路斯价值为1*1 + 2*(-3+7) + 3*(-6+2) + 4*5 = 17。Theofanis想知道数组的任何划分中塞浦路斯价值的最大值是多少。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
- 每个测试用例包含两行。
- 第一行包含一个整数n（1≤n≤10^5）——数组的大小。
- 第二行包含n个整数a_1, a_2, ..., a_n（-10^8≤a_i≤10^8）——数组的元素。
- 保证所有测试用例的n之和不超过2*10^5。

输出：
- 对于每个测试用例，打印一个整数——数组a的塞浦路斯价值的最大值。

示例：
输入：
4
6
1 -3 7 -6 2 5
4
2 9 -5 -3
8
-3 -4 2 -5 1 10 17 23
1
830

输出：
32
4
343
830

注意：
- 在第一个测试用例中，为了得到最大的塞浦路斯价值，我们将数组划分为[1][-3][7][-6][2][5]，这给出的塞浦路斯价值为Σ(i=1 to k) i * sum_i = 1*1 + 2*(-3) + 3*7 + 4*(-6) + 5*2 + 6*5 = 32。
- 在第二个测试用例中，我们将数组划分为[2][9,-5,-3]，这给出的塞浦路斯价值为Σ(i=1 to k) i * sum_i = 1*2 + 2*(9 + (-5) + (-3)) = 4。题目大意： Theofanis在睡前容易对问题过于着迷，并且经常做噩梦。为了解决他的困扰，他去看医生Dr. Emix。在他的最新噩梦中，他有一个大小为n的数组a，并希望将其划分为非空子数组，使得每个元素恰好位于一个子数组中。例如，数组[1,-3,7,-6,2,5]可以划分为[1],[-3,7],[-6,2],[5]。这种划分的塞浦路斯价值（Cypriot value）等于Σ(i=1 to k) i * sum_i，其中k是我们将数组划分成的子数组的数量，sum_i是第i个子数组的和。例如，上述划分的塞浦路斯价值为1*1 + 2*(-3+7) + 3*(-6+2) + 4*5 = 17。Theofanis想知道数组的任何划分中塞浦路斯价值的最大值是多少。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 - 每个测试用例包含两行。 - 第一行包含一个整数n（1≤n≤10^5）——数组的大小。 - 第二行包含n个整数a_1, a_2, ..., a_n（-10^8≤a_i≤10^8）——数组的元素。 - 保证所有测试用例的n之和不超过2*10^5。 输出： - 对于每个测试用例，打印一个整数——数组a的塞浦路斯价值的最大值。 示例： 输入： 4 6 1 -3 7 -6 2 5 4 2 9 -5 -3 8 -3 -4 2 -5 1 10 17 23 1 830 输出： 32 4 343 830 注意： - 在第一个测试用例中，为了得到最大的塞浦路斯价值，我们将数组划分为[1][-3][7][-6][2][5]，这给出的塞浦路斯价值为Σ(i=1 to k) i * sum_i = 1*1 + 2*(-3) + 3*7 + 4*(-6) + 5*2 + 6*5 = 32。 - 在第二个测试用例中，我们将数组划分为[2][9,-5,-3]，这给出的塞浦路斯价值为Σ(i=1 to k) i * sum_i = 1*2 + 2*(9 + (-5) + (-3)) = 4。