Max Subarray Sum with Mandatory Negative

You are given T test cases. For each test case, you are given an integer N and an array of N integers. Your task is to find the maximum sum of a contiguous subarray that must include at least one negative integer. If there is no contiguous subarray containing a negative integer, print -1.

Note: A contiguous subarray is a sequence of consecutive elements from the original array. The answer for each test case is defined as:

\( answer = \max_{\substack{1 \leq i \leq j \leq N \\ \exists k \in [i, j]: a_k < 0}} \sum_{t=i}^{j} a_t \)

If no subarray satisfies the condition (i.e. the array has no negative numbers), output -1.

inputFormat

The input is read from standard input and has the following format:

T
N_1
a1 a2 ... aN1
N_2
a1 a2 ... aN2
...
N_T
a1 a2 ... aN_T

Where:

• T is the number of test cases.
• For each test case, the first line contains an integer N, the number of elements in the array.
• The next line contains N space-separated integers.

outputFormat

For each test case output a single line containing the maximum sum of a contiguous subarray that contains at least one negative integer. If no such subarray exists, output -1.

## sample

6
5
1 2 -3 4 5
4
1 2 3 4
6
-1 -2 -3 -4 -5 -6
1
-1
8
1 2 3 -1 2 3 4 5
3
-5 1 -1

9
-1
-1
-1
19
1

</p>