A. Жили и операции с массивом
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Глубоко в дикой местности Жили и Джили обнаружили скопление полянок, на которых присутствует абстрактная логика. В логике некоторых из этих полянок присутствуют несоответствия, из-за которых они могут разрушиться в любой момент. Они надеются так передать логику между соседними полянками с помощью продуманных механизмов передачи, чтобы в конечном итоге как можно больше полянок смогли восстановить логическую стабильность.

Дан массив $$$a$$$ из $$$n$$$ целых чисел. Вы можете выполнять следующую операцию любое количество раз:

  • Выбрать индекс $$$i$$$ ($$$1 \le i \lt n$$$) и присвоить $$$a_i\gets a_i+a_{i+1}$$$.

Каждый индекс можно выбрать не более одного раза.

Найдите максимальное количество целых положительных чисел в итоговом массиве после выполнения всех операций.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных содержится одно целое число $$$n$$$ ($$$2\leq n \leq 2\cdot 10^5$$$).

Во второй строке каждого набора входных данных содержатся $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9\leq a_i\leq 10^9$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot10^5$$$.

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

Для каждого набора входных данных необходимо вывести одну строку, содержащую целое число $$$k$$$ — количество положительных чисел в конечной последовательности.

Пример
Входные данные
4
5
0 -1 3 -3 0
5
0 -2 1 2 3
5
0 1 0 1 0
2
1000000000 -1000000000
Выходные данные
3
5
4
1
Примечание

В первом наборе входных данных над массивом $$$a$$$ выполняются следующие операции:

$$$[0,-1,3,-3,0]\to [0,\color{red}{2},3,-3,0]\to [\color{red}{2},2,3,-3,0]$$$.

В итоговом массиве содержится $$$3$$$ положительных числа, и можно доказать, что это максимальное количество целых положительных чисел.

Во втором наборе входных данных итоговый массив может быть $$$[4,4,6,5,3]$$$, его можно получить следующим образом:

$$$[0,-2,1,2,3]\to [0,-2,1,\color{red}{5},3]\to [0,-2,\color{red}{6},5,3]\to [0,\color{red}{4},6,5,3]\to [\color{red}{4},4,6,5,3]$$$.

В третьем наборе входных данных конечный массив может быть $$$[1,1,1,1,0]$$$, его можно получить следующим образом:

$$$[0,1,0,1,0]\to [\color{red}{1},1,0,1,0]\to [1,1,\color{red}{1},1,0]$$$.