CF1868E.Min-Sum-Max

Tom is waiting for his results of Zhongkao examination. To ease the tense atmosphere, his friend, Daniel, decided to play a game with him. This game is called "Divide the Array".

The game is about the array $a$ consisting of $n$ integers. Denote $[l,r]$ as the subsegment consisting of integers $a_l,a_{l+1},\ldots,a_r$.

Tom will divide the array into contiguous subsegments $[l_1,r_1],[l_2,r_2],\ldots,[l_m,r_m]$, such that each integer is in exactly one subsegment. More formally:

• For all $1\le i\le m$, $1\le l_i\le r_i\le n$;
• $l_1=1$, $r_m=n$;
• For all $1 \lt i\le m$, $l_i=r_{i-1}+1$.

Denote $s_{i}=\sum_{k=l_i}^{r_i} a_k$, that is, $s_i$ is the sum of integers in the $i$-th subsegment. For all $1\le i\le j\le m$, the following condition must hold:

$$\\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 believes that the more subsegments the array $a$ is divided into, the better results he will get. So he asks Daniel to find the maximum number of subsegments among all possible ways to divide the array $a$. You have to help him find it.

汤姆正在等待他的中考成绩。为了缓解紧张的气氛，他的朋友丹尼尔决定和他玩一个游戏，这个游戏叫做“分割数组”。

游戏涉及一个由 $n$ 个整数组成的数组 $a$。记 $[l,r]$ 为由整数 $a_l, a_{l+1}, \ldots, a_r$ 构成的连续子段。

汤姆将把该数组划分为若干个连续子段 $[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.$$

汤姆认为，数组 $a$ 被划分出的子段数量越多，他最终取得的成绩就越好。因此，他请丹尼尔找出在所有合法划分方式中，子段数量的最大值。你需要帮助他求出这个最大值。

The first line of input contains a single integer $t$ ($1\le t\le 50$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1\le n\le 300$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-10^9\le a_i\le 10^9$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.

输入的第一行包含一个整数 $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$。

For each test case, output a single integer — the maximum number of subsegments among all possible ways to divide the array $a$.

对于每个测试用例，输出一个整数——在所有可能的数组 $a$ 划分方式中，子区间的最大数量。

In the first test case, Daniel can divide the array into $[-1]$ and $[5,4]$, and $s=[-1,9]$. It can be shown that for any $i=j$, the condition in the statement is already satisfied, and for $i=1,j=2$, we have $\min(-1,9)\le (-1)+9\le \max(-1,9)$.

In the second test case, if Daniel divides the array into $[2023]$ and $[2043]$, then for $i=1,j=2$ we have $2023+2043 \gt \max(2023,2043)$, so the maximum number of subsegments is $1$.

In the third test case, the optimal way to divide the array is $[1,4,7],[-1],[5,-4]$.

In the fourth test case, the optimal to divide the array way is $[-4,0,3,-18],[10]$.

In the fifth test case, Daniel can only get one subsegment.

在第一个测试用例中，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 只能得到一个子段。