← 返回题目列表

Codeforces · 1669/F

F. 吃糖果

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

桌子上从左到右放着 $$$n$$$ 糖果。糖果从左到右编号。第 $$$i$$$ 糖果的重量为 $$$w_i$$$。爱丽丝和鲍勃吃糖果。

爱丽丝可以从左边吃任意数量的糖果(她不能跳过糖果,她要连续吃掉它们)。

鲍勃可以从右边吃任意数量的糖果(他不能跳过糖果,他会连续吃掉它们)。

当然,如果爱丽丝吃了一颗糖果,鲍勃就不能吃它(反之亦然)。

他们想要公平。他们的目标是吃下相同总重量的糖果。他们总共最多可以吃多少颗糖果?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — 桌子上的糖果数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$w_1, w_2, \dots, w_n$$$ ($$$1 \leq w_i \leq 10^4$$$) - 从左到右糖果的重量。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。

输出

对于每个测试用例,打印一个整数 - Alice 和 Bob 在满足条件时总共可以吃的最大糖果数量。

示例

输入 #1

4
3
10 20 10
6
2 1 4 2 4 1
5
1 2 4 8 16
9
7 3 20 5 15 1 11 8 10

输出 #1

2
6
0
7

注意

对于第一个测试用例,Alice 将从左边吃一颗糖果,Bob 将从右边吃一颗糖果。没有更好的方法让他们吃掉相同的总重量。答案是 $$$2$$$ 因为他们总共吃了两颗糖果。

对于第二个测试用例,Alice 会吃掉左边的前三颗糖果(总重量为 $$$7$$$),Bob 会吃掉右边的前三颗糖果(总重量为 $$$7$$$)。他们不能再吃更多的糖果了,因为所有的糖果都已经吃完了,所以答案是$$$6$$$(因为他们总共吃了六颗糖果)。

对于第三个测试用例,Alice 和 Bob 不可能吃相同的非零重量,因此答案是 $$$0$$$。

对于第四个测试用例,Alice 将吃重量为 $$$[7, 3, 20]$$$ 的糖果,Bob 将吃重量为 $$$[10, 8, 11, 1]$$$ 的糖果,他们各自吃 $$$30$$$ 重量的糖果。没有更好的分区,所以答案是 $$$7$$$。