← 返回题目列表

Codeforces · 2224/A

A. 智力与阵列操作

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

在荒野深处,芝莉和吉莉发现了一系列包含抽象逻辑的聚集地。有些聚集地逻辑上存在不一致的错误,随时可能崩溃。他们希望通过合理的转移安排,在相邻的聚集地之间传递逻辑,让尽可能多的聚集地最终恢复逻辑的稳定性。

给定一个由 $$$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$$$,即最终序列中正数的数量。

示例

输入
复制

4
5
0 -1 3 -3 0
5
0 -2 1 2 3
5
0 1 0 1 0
2
1000000000 -1000000000

输出
复制

3
5
4
1

注意

在第一个测试用例中,数组 $$$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]$$$。