B. Optimal Partitiontime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an array a consisting of n integers. You should divide a into continuous non-empty subarrays (there are 2^{n-1} ways to do that).Let s=a_l+a_{l+1}+\ldots+a_r. The value of a subarray a_l, a_{l+1}, \ldots, a_r is:   (r-l+1) if s>0, 0 if s=0, -(r-l+1) if s<0.  What is the maximum sum of values you can get with a partition?InputThe input consists of multiple test cases. The first line contains a single integer t (1 \le t \le 5 \cdot 10^5) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer n (1 \le n \le 5 \cdot 10^5).The second line of each test case contains n integers a_1, a_2, ..., a_n (-10^9 \le a_i \le 10^9).It is guaranteed that the sum of n over all test cases does not exceed 5 \cdot 10^5.OutputFor each test case print a single integer — the maximum sum of values you can get with an optimal parition.ExampleInput
5
3
1 2 -3
4
0 -2 3 -4
5
-1 -2 3 -1 -1
6
-1 2 -3 4 -5 6
7
1 -1 -1 1 -1 -1 1
Output
1
2
1
6
-1
NoteTest case 1: one optimal partition is [1, 2], [-3]. 1+2>0 so the value of [1, 2] is 2. -3<0, so the value of [-3] is -1. 2+(-1)=1.Test case 2: the optimal partition is [0, -2, 3], [-4], and the sum of values is 3+(-1)=2.
5
3
1 2 -3
4
0 -2 3 -4
5
-1 -2 3 -1 -1
6
-1 2 -3 4 -5 6
7
1 -1 -1 1 -1 -1 1

1 2 1 6 -1 
['data structures', 'dp', '*2100']