Глубоко в дикой местности Жили и Джили обнаружили скопление полянок, на которых присутствует абстрактная логика. В логике некоторых из этих полянок присутствуют несоответствия, из-за которых они могут разрушиться в любой момент. Они надеются так передать логику между соседними полянками с помощью продуманных механизмов передачи, чтобы в конечном итоге как можно больше полянок смогли восстановить логическую стабильность.
Дан массив $$$a$$$ из $$$n$$$ целых чисел. Вы можете выполнять следующую операцию любое количество раз:
Каждый индекс можно выбрать не более одного раза.
Найдите максимальное количество целых положительных чисел в итоговом массиве после выполнения всех операций.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$ — количество положительных чисел в конечной последовательности.
450 -1 3 -3 050 -2 1 2 350 1 0 1 021000000000 -1000000000
3541
В первом наборе входных данных над массивом $$$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]$$$.
