310675: CF1868E. Min-Sum-Max

E. Min-Sum-Maxtime limit per test5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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< 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.

Input

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$.

Output

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

ExampleInput

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

Output

2
1
3
2
1
6
5
3

Note

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>\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.

题目大意：
这个题目是关于将一个由n个整数组成的数组a划分为若干个连续的子段的问题。要求每个整数恰好位于一个子段中。子段的总和满足一个特定的条件，即对于任意1≤i≤j≤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\]
其中，\(s_k\)是第k个子段中整数的和。汤姆认为，数组a被划分的子段越多，他得到的中考结果就越好。因此，他要求丹尼尔找到所有可能的划分方式中子段的最大数量。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤50），表示测试用例的数量。
- 每个测试用例的第一行包含一个整数n（1≤n≤300），表示数组a的长度。
- 每个测试用例的第二行包含n个整数\(a_1, a_2, \ldots, a_n\)（-10^9≤ai≤10^9），表示数组a的元素。
- 保证所有测试用例的n之和不超过1000。

输出：
- 对于每个测试用例，输出一个整数，表示所有可能的划分方式中子段的最大数量。题目大意： 这个题目是关于将一个由n个整数组成的数组a划分为若干个连续的子段的问题。要求每个整数恰好位于一个子段中。子段的总和满足一个特定的条件，即对于任意1≤i≤j≤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\] 其中，\(s_k\)是第k个子段中整数的和。汤姆认为，数组a被划分的子段越多，他得到的中考结果就越好。因此，他要求丹尼尔找到所有可能的划分方式中子段的最大数量。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤50），表示测试用例的数量。 - 每个测试用例的第一行包含一个整数n（1≤n≤300），表示数组a的长度。 - 每个测试用例的第二行包含n个整数\(a_1, a_2, \ldots, a_n\)（-10^9≤ai≤10^9），表示数组a的元素。 - 保证所有测试用例的n之和不超过1000。 输出： - 对于每个测试用例，输出一个整数，表示所有可能的划分方式中子段的最大数量。