E. Max Subarray Sum
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$.

The cost of an array is the maximum sum of any of it's subarrays$$$^{\text{∗}}$$$. Note the cost of an empty array is $$$0$$$.

You must choose exactly one non-empty subarray and remove it, then concatenate the remaining part without changing the order. For example, if the array is $$$[1, 5, 2, 4]$$$ and you remove the subarray from index $$$2$$$ to $$$3$$$, the resulting array becomes $$$[1, 4]$$$.

Find the maximum possible cost of the array over all possible subarray removals.

$$$^{\text{∗}}$$$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 2 \cdot 10^5$$$) — the number of test cases.

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — 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 testcase, output a single integer — the maximum cost of the given array.

Example
Input
3
4
1 2 3 4
3
1 -1 1
1
-1
Output
9
2
0
Note

In the first test case, the maximum cost is achieved by removing the first element.

In the second test case, the maximum cost is achieved by removing the second element.