E. Пчеленок и подотрезки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пчеленок решил сделать Миле подарок. Пчеленок уже купил массив $$$a$$$ длины $$$n$$$, но дарить просто массив слишком банально. Вместо этого он решил подарить Миле подотрезки этого массива!

Пчеленок хочет, чтобы его подарок был красивым, поэтому он решил выбрать $$$k$$$ непересекающихся подотрезков массива $$$[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)$$$).

Пчеленок также хочет, чтобы его подарок был как можно больше, поэтому он просит вас узнать, при каком максимальном $$$k$$$ он сможет сделать подарок Миле!

Входные данные

Первая строка содержит одно целое число $$$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$$$.

Пример
Входные данные
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
2
3
1