题目描述

给你一个长度为 $n$ 的数组 $A = (a_1, a_2, \dots, a_n)$

• 1、从中选取一个 连续 的区间 $[l, r] (1 \le l \le r \le n)$，得到数组 $B = (a_l, a_{l+1}, \dots, a_r)$
• 2、计算这个数组 $B$ 的 前缀和 数组 $C = (c_1, c_2, \dots, c_k)$，其中
  • $C$ 数组的长度为：$k=r-l+1$
  • $c_i = \sum \limits_{j=1}^{i}B_j = B_1+B_2+B_3+\dots+B_i$

找出这样一个区间 $[l, r]$，使其对应的前缀和序列 $C$ 中 包含最多数量的 $0$。请输出这个最大数量。

输入格式

本题包含多组测试数据。

第一行输入一个正整数 $T$，表示数据组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

• 第一行输入一个正整数 $n$。
• 第二行输入 $n$ 个整数，表示温度序列 $a_1, a_2, \dots, a_n$。

输出格式

对于每组测试数据：

• 输出一行一个非负整数，表示最优情况下前缀和序列中 $0$ 的最大数量。

2
5
-1 0 1 0 0
5
4 2 0 -2 9

3
1

提示

【样例解释 #1】

该样例共有 $2$ 组测试数据。

对于第一组测试数据，温度序列为 $A = [-1, 0, 1, 0, 0]$。最佳选择是选取从第 $1$ 天到第 $5$ 天的时间段，对应的子序列为 $[-1, 0, 1, 0, 0]$。其前缀和序列计算如下：

• $c_1 = -1$
• $c_2 = -1 + 0 = -1$
• $c_3 = -1 + 0 + 1 = 0$
• $c_4 = -1 + 0 + 1 + 0 = 0$
• $c_5 = -1 + 0 + 1 + 0 + 0 = 0$

前缀和序列为 $[-1, -1, 0, 0, 0]$，其中包含 $3$ 个 $0$。这是所有可能的时间段中能得到的最大数量，因此答案是 $3$。

对于第二组测试数据，温度序列为 $A = [4, 2, 0, -2, 9]$。最佳选择是选取从第 $2$ 天到第 $4$ 天的时间段，对应的子序列为 $[2, 0, -2]$。其前缀和序列计算如下：

• $c_1 = 2$
• $c_2 = 2 + 0 = 2$
• $c_3 = 2 + 0 + (-2) = 0$

前缀和序列为 $[2, 2, 0]$，其中包含 $1$ 个 $0$。这是所有可能的时间段中能得到的最大数量，因此答案是 $1$。

【数据范围】

对于 $100\%$ 的数据，保证 $1 \le T \le 5$，$1 \le n \le 10^6$，$-10^6 \le a_i \le 10^6$。

记 $V$ 为所有 $a_i$ 的绝对值的最大值，即 $\max \limits_{i=1}^{n} |a_i|$。

• 特殊性质 A：保证 $n = 10^5$，且序列 $A$ 随机生成。随机方式是在所有符合数据范围的序列 $A$ 中，等概率均匀随机抽取得到输入时的序列 $A$。
• 特殊性质 B：保证对于每个 $i \in [1,n]$，$a_i \ge 0$。
• 参考答案