CF2237C.Duck Surplus

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})$.

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.

幽灵杰（Ja the Ghost）又在玩橡皮鸭了！一共有 $n$ 堆橡皮鸭，从左到右排成一行。初始时，第 $i$ 堆包含 $a_i$ 只橡皮鸭。

只要序列 $a$ 尚未按非递减顺序排列，杰就必须执行以下操作：

• 选择两个相邻的堆，使得左边堆中的鸭子数量严格大于右边堆中的鸭子数量；杰交换这两堆的位置，然后将新左边堆中的鸭子数量加到新右边堆中。
  形式化地，选择一个下标 $i$，满足 $1 \le i < n$ 且 $a_i > a_{i+1}$；然后将相邻二元组 $(a_i, a_{i+1})$ 替换为 $(a_{i+1},\, a_i + a_{i+1})$。

例如，若两个相邻堆分别有 $7$ 只和 $3$ 只橡皮鸭，则操作后它们变为 $3$ 只和 $10$ 只橡皮鸭。

在每一步中，杰可任选一个满足上述条件的下标 $i$。可以证明：无论他如何选择，该过程最终总会终止，且此时序列已按非递减顺序排列。

杰希望使过程结束时最大一堆中的橡皮鸭数量尽可能少。请确定该最大堆大小的最小可能值。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 表示堆的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1\le a_i\le 10^9$）—— 表示每堆中鸭子的数量。

保证所有测试用例的 $n$ 之和不超过 $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 underlined numbers are the adjacent pair just obtained by the operation.

In the first test case, the sequence is already sorted in nondecreasing order. Therefore Ja does not perform any operation, and the answer is $5$.

In the second test case, Ja has only one possible operation: $$ [7,3]\to [\underline{3},\underline{10}]. $$ The sequence is then sorted, so the answer is $10$.

In the third test case, Ja can perform the following operations: $$ [3,2,1]\to [\underline{2},\underline{5},1]\to [2,\underline{1},\underline{6}]\to [\underline{1},\underline{3},6]. $$ The largest pile contains $6$ ducks. If Ja first chooses the last two piles instead, the final largest pile would contain $7$ ducks. Therefore the answer is $6$.

In the fourth test case, Ja cannot choose the first two piles at the beginning, because $2$ is not greater than $2$. One possible process is $$ [2,2,1,3,3]\to [2,\underline{1},\underline{3},3,3]\to [\underline{1},\underline{3},3,3,3]. $$ Thus the answer is $3$.

In the fifth test case, one optimal process is $$ [3,1,4,2]\to [\underline{1},\underline{4},4,2]\to [1,4,\underline{2},\underline{6}]\to [1,\underline{2},\underline{6},6]. $$ Therefore the answer is $6$.

在以下变换中，两个带下划线的数字是刚通过该操作得到的相邻数对。

在第一个测试用例中，序列已按非递减顺序排好序。因此 Ja 不执行任何操作，答案为 $5$。

在第二个测试用例中，Ja 只有一种可能的操作：

\[7,3\]\\to \[\\underline{3},\\underline{10}\].

此时序列已排序，因此答案为 $10$。

在第三个测试用例中，Ja 可执行如下操作：

\[3,2,1\]\\to \[\\underline{2},\\underline{5},1\]\\to \[2,\\underline{1},\\underline{6}\]\\to \[\\underline{1},\\underline{3},6\].

此时最大堆包含 $6$ 只鸭子。若 Ja 起初先选择最后两个堆，则最终最大堆将包含 $7$ 只鸭子。因此答案为 $6$。

在第四个测试用例中，Ja 开始时不能选择前两个堆，因为 $2$ 并不大于 $2$。一种可行的过程为：

\[2,2,1,3,3\]\\to \[2,\\underline{1},\\underline{3},3,3\]\\to \[\\underline{1},\\underline{3},3,3,3\].

因此答案为 $3$。

在第五个测试用例中，一种最优过程为：

\[3,1,4,2\]\\to \[\\underline{1},\\underline{4},4,2\]\\to \[1,4,\\underline{2},\\underline{6}\]\\to \[1,\\underline{2},\\underline{6},6\].

因此答案为 $6$。