B'You 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: The input consists of multiple test cases. The first line contains a single integer t ( 1 <= t <= 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 <= n <= 5 cdot 10^5 ). The second line of each test case contains n integers a_1 , a_2 , ..., a_n ( -10^9 <= a_i <= 10^9 ). It is guaranteed that the sum of n over all test cases does not exceed 5 cdot 10^5 . For each test case print a single integer -- the maximum sum of values you can get with an optimal parition. Test 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 . '...