Pchelyonok and Segments

题意翻译

Pchelyonok决定给Mila一件礼物。Pchelyonok已经“买”了一个长度为 $n$ 的数组 $a$，但他觉得送一个数组太普通了。他决定将这个数组中的一些区间送给Mila！ Pchelyonok想让他的礼物更漂亮，因此他决定从数组选择 $k$ 个不相交的区间,满足： * 第一个区间的长度是 $k$，第二个区间的长度是 $k-1$，...，第 $k$ 个区间的长度是 $1$。 * 对任意$i \lt j$，第 $i$ 个区间在第 $j$ 个区间左边。（即 $r_i \lt l_j$）。 * 这些区间内的数之和严格单调递增。（用符号语言说就是：令 $sum(l,r)=\Sigma_{i=l}^{r}a_i$，则 $sum(l_1,r_1) \lt sum(l_2,r_2) \lt...\lt sum(l_k,r_k)$ ） Pchelenok希望他的礼物尽可能漂亮，所以他请你找到满足上述条件的 $k$ 的最大值。

题目描述

Pchelyonok decided to give Mila a gift. Pchelenok has already bought an array $ a $ of length $ n $ , but gifting an array is too common. Instead of that, he decided to gift Mila the segments of that array! Pchelyonok wants his gift to be beautiful, so he decided to choose $ k $ non-overlapping segments of the array $ [l_1,r_1] $ , $ [l_2,r_2] $ , $ \ldots $ $ [l_k,r_k] $ such that: - the length of the first segment $ [l_1,r_1] $ is $ k $ , the length of the second segment $ [l_2,r_2] $ is $ k-1 $ , $ \ldots $ , the length of the $ k $ -th segment $ [l_k,r_k] $ is $ 1 $ - for each $ i<j $ , the $ i $ -th segment occurs in the array earlier than the $ j $ -th (i.e. $ r_i<l_j $ ) - the sums in these segments are strictly increasing (i.e. let $ sum(l \ldots r) = \sum\limits_{i=l}^{r} a_i $ — the sum of numbers in the segment $ [l,r] $ of the array, then $ sum(l_1 \ldots r_1) < sum(l_2 \ldots r_2) < \ldots < sum(l_k \ldots r_k) $ ). Pchelenok also wants his gift to be as beautiful as possible, so he asks you to find the maximal value of $ k $ such that he can give Mila a gift!

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The next $ 2 \cdot t $ lines contain the descriptions of test cases. The description of each test case consists of two lines. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of the array. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \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 $ 10^5 $ .

输出格式

For each test case, print the maximum possible value of $ k $ .

输入输出样例

输入样例 #1

5
1
1
3
1 2 3
5
1 1 2 2 3
7
1 2 1 1 3 2 6
5
9 6 7 9 7

输出样例 #1

1
1
2
3
1