← 返回题目列表

Codeforces · 2237/C

C. 鸭剩余

中文机器翻译题面 查看原题

幽灵贾又在玩橡皮鸭了!有 $$$n$$$ 堆橡皮鸭从左到右排成一排。最初,第 $$$i$$$ 堆包含 $$$a_i$$$ 橡皮鸭。

虽然序列 $$$a$$$ 未按非降序排序,但 Ja 必须 执行以下操作:

  • 选择两个相邻的堆,使得左侧堆比右侧堆包含更多鸭子。 Ja 交换这两堆,然后将新的左堆中的鸭子数量添加到新的右堆中。

    正式地,选择一个索引 $$$i$$$,使得 $$$1\le i \lt n$$$ 和 $$$a_i \gt a_{i+1}$$$。然后将相邻对 $$$(a_i,a_{i+1})$$$ 替换为 $$$(a_{i+1},a_i+a_{i+1})$$$。

例如,如果两个相邻堆包含 $$$7$$$ 和 $$$3$$$ 橡皮鸭,则操作后它们包含 $$$3$$$ 和 $$$10$$$ 橡皮鸭。

Ja可以在每一步中选择满足上述条件的任何索引。可以证明,无论他的选择如何,该过程最终都会以按非降序排序的序列结束。

Ja 希望流程结束时最大的一堆包含尽可能少的橡皮鸭。确定最大堆的最小可能值。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。

输出

对于每个测试用例,输出一个整数 - 最大堆的最小可能值。

示例

输入
复制

10
4
1 2 2 5
2
7 3
3
3 2 1
5
2 2 1 3 3
4
3 1 4 2
5
1 4 3 2 5
6
6 2 5 1 4 3
7
2 7 1 6 3 5 4
8
8 1 7 2 6 3 5 4
5
1000000000 999999999 999999998 999999997 999999996

输出
复制

5
10
6
3
6
14
21
26
36
4999999990

注意

在下面的变换中,下划线的两个数是刚刚运算得到的相邻对。

在第一个测试用例中,序列已经按非降序排序。因此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$$$。