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

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

For each test case, output a single integer — the maximum number of subsegments among all possible ways to divide the array $ 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>\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.