Pchelyonok and Segments
Contest: Codeforces Round 750 (Div. 2)
Difficulty rating: 2000
Tags: binary search, data structures, dp, greedy, math

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!

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
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

Example output:
1
1
2
3
1

Editorial:
Let's notice that $$$k$$$ can be the answer, only if the sum of lengths of the segments does not exceed the number of elements in the array, that is $$$\frac{k \cdot (k + 1)}{2} \le n$$$. From this inequation we can get that $$$k$$$ is less than $$$\sqrt{2n}$$$, and when $$$n$$$ hits its maximal value, it does not exceed $$$447$$$.
Let $$$dp_{i,j}$$$ be the maximal sum on the segment of length $$$j$$$, with that we have already considered all elements on the suffix $$$i$$$ (that is, elements with indices $$$i, i + 1, \ldots, n$$$) and have already chosen segments with lengths $$$j, j - 1, \ldots, 1$$$, in which the sums increase. Let's learn to recalculate the values of dynamics. We can either not include the $$$i$$$-th element in the segment of length $$$j$$$, then we need refer to the value of dynamics $$$dp_{i+1,j}$$$, or include the $$$i$$$-th element, and then we are interested in the value of dynamics $$$dp_{i+j,j-1}$$$ — if it's greater than the sum on the segment $$$i, i + 1, \ldots, i + j - 1$$$, then we can take $$$j$$$ segments with lengths from $$$j$$$ to $$$1$$$ on the suffix $$$i$$$, answ otherwise we cannot take such segments on the suffix $$$i$$$. We need to take the maximum among these two cases in order to maximize the sum. To calculate the sum on a segment you can use prefix sums.
Asymptotic behavior of this solution — $$$O(n \cdot \sqrt{n})$$$.