桌子上从左到右放着 $$$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$$$。