U463280 Array Gerrymandering

忙碌的海狸决定竞选总统。不幸的是，他唯一的对手懒惰狐猴太强大了，忙碌阿狸无法用正常手段赢得选举。因此，他做了所有优秀政客都会做的事情：通过 "选区划分 "来操纵选举！ 

每个城市投票选出懒惰狐猴或忙碌阿狸担任总统，如果投票给懒惰狐猴，则代表 $0$；如果投票给忙碌阿狸，则代表 $1$。不过，"忙碌的海狸 "可以把 $n$ 个城市分成 $k$ 个由连续城市组成的 **非空** 区块，每个区块就是一个区。对于从 $1$ 到 $n$ 的每一个 $k$ 值，"忙碌的海狸 "希望最大限度地增加支持他的票数 **严格地** 多于支持 "懒惰的狐猴 "的票数的地区数量。 你能帮助 "忙碌的海狸 "找到严格意义上 $k=1,...,n$ 的票数比 "懒惰的狐猴 "多的地区的最大数目吗？

无

无

**【数据范围】** 对于所有测试数据保证：$T\le 10^5,\sum n\le 2\times 10^5,0\le a_i\le 1$。 | 测试点编号 | $\sum n\leq$ | 特殊性质或约束 | | :----------: | :----------: | :----------: | | $1,2,3$ | $100$ | \ | | $4,5,6$ | $2000$ | \ | | $7,8,9,10$ | $2\times 10^5$ | $T$ 组数据 $0$ 的总数量不超过 $20$ | | $11,12,13$ | $2\times 10^5$ | 数据随机生成 | | $14,15,16,17,18,19,20$ | $2\times 10^5$ | \ |