汤姆正在等待中考成绩。为了缓解紧张的气氛,他的朋友丹尼尔决定和他玩一个游戏。这个游戏叫做“分阵”。
游戏涉及由 $$$n$$$ 整数组成的数组 $$$a$$$。将 $$$[l,r]$$$ 表示为由整数 $$$a_l,a_{l+1},\ldots,a_r$$$ 组成的子段。
Tom 会将数组划分为连续的子段 $$$[l_1,r_1],[l_2,r_2],\ldots,[l_m,r_m]$$$,这样每个整数都恰好位于一个子段中。更正式地说:
- 对于所有 $$$1\le i\le m$$$, $$$1\le l_i\le r_i\le n$$$;
- $$$l_1=1$$$, $$$r_m=n$$$;
- 对于所有 $$$1< i\le m$$$,$$$l_i=r_{i-1}+1$$$。
表示$$$s_{i}=\sum_{k=l_i}^{r_i} a_k$$$,即$$$s_i$$$是第$$$i$$$个子段中的整数之和。对于所有 $$$1\le i\le j\le m$$$,必须满足以下条件:
$$$$$$ \min_{i\le k\le j} s_k \le \sum_{k=i}^j s_k \le \max_{i\le k\le j} s_k。 $$$$$$
Tom 认为,将数组 $$$a$$$ 划分的子段越多,他得到的结果就越好。因此,他要求 Daniel 在所有可能的划分数组 $$$a$$$ 的方法中找到子段的最大数量。你必须帮助他找到它。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1\le t\le 50$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 300$$$) — 数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9\le a_i\le 10^9$$$) — 数组 $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$。
输出
对于每个测试用例,输出一个整数 - 划分数组 $$$a$$$ 的所有可能方法中子段的最大数量。
示例
输入 #1
8 3 -1 5 4 2 2023 2043 6 1 4 7 -1 5 -4 5 -4 0 3 -18 10 1 998244853 10 -4 2 5 -10 4 8 2 9 -15 7 7 -7 3 8 -9 -2 2 4 4 -5 5 -2 -5
输出 #1
2 1 3 2 1 6 5 3
注意
在第一个测试用例中,Daniel 可以将数组分为 $$$[-1]$$$ 和 $$$[5,4]$$$,以及 $$$s=[-1,9]$$$。可以看出,对于任何$$$i=j$$$,语句中的条件已经满足,而对于$$$i=1,j=2$$$,我们有$$$\min(-1,9)\le (-1)+9\le \max(-1,9)$$$。
在第二个测试用例中,如果 Daniel 将数组分为 $$$[2023]$$$ 和 $$$[2043]$$$,则对于 $$$i=1,j=2$$$,我们有 $$$2023+2043>\max(2023,2043)$$$,因此子段的最大数量为 $$$1$$$。
在第三个测试用例中,划分数组的最佳方式是 $$$[1,4,7],[-1],[5,-4]$$$。
在第四个测试用例中,最佳的数组划分方式是$$$[-4,0,3,-18],[10]$$$。
在第五个测试用例中,Daniel 只能得到一个子段。