在荒野深处,芝莉和吉莉发现了一系列包含抽象逻辑的聚集地。有些聚集地逻辑上存在不一致的错误,随时可能崩溃。他们希望通过合理的转移安排,在相邻的聚集地之间传递逻辑,让尽可能多的聚集地最终恢复逻辑的稳定性。
给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。您可以多次执行以下操作:
- 选择一个索引 $$$i$$$ ($$$1 \le i \lt n$$$) 并分配 $$$a_i\gets a_i+a_{i+1}$$$。
每个索引都可以选择 最多一次.
查找所有操作后最终数组中正整数的最大数量。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\leq n \leq 2\cdot 10^5$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9\leq a_i\leq 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。
输出
对于每个测试用例,您应该输出一行包含整数 $$$k$$$,即最终序列中正数的数量。
示例
输入复制
450 -1 3 -3 050 -2 1 2 350 1 0 1 021000000000 -1000000000
输出复制
3541
注意
在第一个测试用例中,数组 $$$a$$$ 通过以下过程进行操作:
$$$[0,-1,3,-3,0]\到 [0,\color{red}{2},3,-3,0]\到 [\color{red}{2},2,3,-3,0]$$$。
最终数组中有$$$3$$$个正数,可以证明这是正整数的最大个数。
在第二个测试用例中,最终的数组可以是:$$$[4,4,6,5,3]$$$,其操作过程如下:
$$$[0,-2,1,2,3]\到 [0,-2,1,\color{red}{5},3]\到 [0,-2,\color{red}{6},5,3]\到 [0,\color{red}{4},6,5,3]\到 [\color{red}{4},4,6,5,3]$$$。
在第三个测试用例中,最终的数组可以是:$$$[1,1,1,1,0]$$$,其操作过程如下:
$$$[0,1,0,1,0]\到 [\color{red}{1},1,0,1,0]\到 [1,1,\color{red}{1},1,0]$$$。