Ja the Ghost is playing with rubber ducks again! There are (n) piles of rubber ducks arranged in a row from left to right. Initially, the (i)-th pile contains (a_i) rubber ducks. While the sequence (a) is not sorted in nondecreasing order, Ja must perform the following operation: Choose two adjacent piles such that the left pile contains more ducks than the right pile. Ja swaps these two piles, and then adds the number of ducks in the new left pile to the new right pile. Formally, choose an index (i) such that (1\le i \lt n) and (a_i \gt a_{i+1}). Then replace the adjacent pair ((a_i,a_{i+1})) with ((a_{i+1},a_i+a_{i+1})). Formally, choose an index (i) such that (1\le i \lt n) and (a_i \gt a_{i+1}). Then replace the adjacent pair ((a_i,a_{i+1})) with ((a_{i+1},a_i+a_{i+1})). For example, if two adjacent piles contain (7) and (3) rubber ducks, then after the operation they contain (3) and (10) rubber ducks. Ja may choose any index satisfying the condition above at each step. It can be shown that, regardless of his choices, the process eventually ends with the sequence sorted in nondecreasing order. Ja wants the largest pile at the end of the process to contain as few rubber ducks as possible. Determine the minimum possible value of the largest pile. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10^4)). The description of the test cases follows. The first line of each test case contains (n) ((1 \le n \le 2 \cdot 10^5)) — the number of piles. The second line of each test case contains (n) integers (a_1, a_2, \ldots, a_n) ((1\le a_i\le 10^9)) — the number of ducks in each pile. It is guaranteed that the sum of (n) over all test cases does not exceed (2 \cdot 10^5). For each test case, output a single integer — the minimum possible value of the largest pile. In the transformations below, the two