← 返回题目列表

Codeforces · 1582/E

E. Pchelyonok 和段

中文机器翻译题面 查看原题

Pchelyonok 决定给 Mila 一份礼物。 Pchelenok 已经购买了一个长度为 $$$n$$$ 的数组 $$$a$$$,但是赠送数组太常见了。相反,他决定将那阵的碎片送给米拉!

Pchelyonok 希望他的礼物很漂亮,因此他决定选择数组 $$$[l_1,r_1]$$$、$$$[l_2,r_2]$$$、$$$\ldots$$$ $$$[l_k,r_k]$$$ 的非重叠段,这样:

- 第一个段 $$$[l_1,r_1]$$$ 的长度为 $$$k$$$,第二个段 $$$[l_2,r_2]$$$ 的长度为 $$$k-1$$$、$$$\ldots$$$,第 $$$k$$$ 段的长度 $$$[l_k,r_k]$$$ 为$$$1$$$
- 对于每个 $$$i<j$$$,第 $$$i$$$ 段出现在数组中早于第 $$$j$$$ 段(即 $$$r_i<l_j$$$)
- 这些段中的总和严格递增(即令 $$$sum(l \ldots r) = \sum\limits_{i=l}^{r} a_i$$$ — 数组的 $$$[l,r]$$$ 段中的数字之和,然后 $$$sum(l_1 \ldots r_1) < sum(l_2 \ldots r_2) < \ldots < sum(l_k \ldots r_k)$$$)。

Pchelenok 也希望他的礼物尽可能漂亮,所以他要求你找到 $$$k$$$ 的最大值,以便他可以给 Mila 一份礼物!

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。接下来的 $$$2 \cdot t$$$ 行包含测试用例的描述。每个测试用例的描述由两行组成。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,打印 $$$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