B'You are given an array of numbers a_1, a_2, ldots, a_n . Your task is to block some elements of the array in order to minimize its cost. Suppose you block the elements with indices 1 <= q b_1 < b_2 < ldots < b_m <= q n . Then the cost of the array is calculated as the maximum of: For example, if n = 6 , the original array is [ 1, 4, 5, 3, 3, 2 ], and you block the elements at positions 2 and 5 , then the cost of the array will be the maximum of the sum of the blocked elements ( 4 + 3 = 7 ) and the sums of the subarrays ( 1 , 5 + 3 = 8 , 2 ), which is max(7,1,8,2) = 8 . You need to output the minimum cost of the array after blocking. The first line of the input contains a single integer t ( 1 <= q t <= q 30 ,000 ) -- the number of queries. Each test case consists of two lines. The first line contains an integer n ( 1 <= q n <= q 10^5 ) -- the length of the array a . The second line contains n elements a_1, a_2, ldots, a_n ( 1 <= q a_i <= q 10^9 ) -- the array a . It is guaranteed that the sum of n over all test cases does not exceed 10^5 . For each test case, output a single number -- the minimum cost of blocking the array. The first test case matches with the array from the statement. To obtain a cost of 7 , you need to block the elements at positions 2 and 4 . In this case, the cost of the array is calculated as the maximum of: So the cost is max(7,5) = 7 . In the second test case, you can block the elements at positions 1 and 4 . In the third test case, to obtain the answer 11 , you can block the elements at positions 2 and 5 . There are other ways to get this answer, for example, blocking positions 4 and 6 . '...