CF2237C Duck Surplus

Ja the Ghost 又开始玩橡胶鸭了！有 $n$ 堆橡胶鸭从左到右排成一行。初始时，第 $i$ 堆有 $a_i$ 只橡胶鸭。 只要序列 $a$ 不是非递减序列，Ja 就必须进行如下操作： - 选择两个相邻的堆，且左边堆的鸭子比右边堆多。Ja 交换这两堆的位置，并且把新左边堆的鸭子数量加到新右边堆上。形式化地说，选择某个索引 $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$ 只橡胶鸭。 Ja 每次可以选择任意一个满足条件的下标 $i$。可以证明，无论他的选择如何，这一过程最终都会以序列变成非递减排列而结束。 Ja 希望最终最大的那一堆鸭子数量尽可能少。请你计算最终最大橡胶鸭堆的最小可能数量。

每组测试包含多组数据。第一行包含测试组数 $t$（$1 \le t \le 10^4$）。接下来是每组数据的描述。 每组数据第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）——橡胶鸭堆的数量。 第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），分别表示每堆鸭子的数量。 保证所有测试组中 $n$ 的总和不超过 $2 \times 10^5$。

对于每组测试数据，输出一个整数，表示最终最大橡胶鸭堆的最小可能数量。

在下面的变换中，下划线的两个数字为本次操作的相邻对。 第一组数据中，序列已经是非递减序列，所以 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 \le 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$。 由 ChatGPT 5 翻译