Vườn quýt của Cam 🍊

Cam là một anh nông dân cần mẫn chăm sóc vườn quýt của mình, nơi có ~N~ giỏ quýt được xếp ngay ngắn thành một hàng dài, đánh số từ 1 đến ~N~. Dựa vào chất lượng, mỗi giỏ quýt ở vị trí ~i~ mang lại cho Cam một giá trị kinh tế ~A_i~ 😉:

• Nếu ~A_i~ > 0: Giỏ quýt đạt chuẩn, mang lại lợi nhuận cho Cam.
• Nếu ~A_i~ < 0: Giỏ quýt bị dập nát, khiến Cam tốn thêm chi phí xử lý và làm giảm lợi nhuận.
• Nếu ~A_i~ = 0: Giỏ quýt ở mức hòa vốn, không sinh lời cũng không gây lỗ.

Trước khi đem bán, Cam được quyền can thiệp vào các giỏ quýt bao nhiêu lần tùy ý (kể cả 0 lần). Mỗi lần, Cam có thể thực hiện thao tác sau:

• Chọn một vị trí ~i~ bất kỳ (1 ≤ ~i~ ≤ ~N~) và nhặt bỏ những quả hỏng, đưa giá trị của giỏ đó về mức hòa vốn, tức là đặt ~A_i~ = 0.

Đến phiên chợ, thương lái yêu cầu Cam phải chọn một đoạn các giỏ nằm liên tiếp nhau để đem ra bán. Tổng lợi nhuận thu về sẽ là tổng giá trị của tất cả các giỏ trong đoạn liên tiếp đó.

Cam muốn sau khi thực hiện các thao tác sơ chế, tổng lợi nhuận của một đoạn liên tiếp đạt được giá trị cao nhất có thể. Dù vậy, vì tiếc công sức chăm bón, Cam không muốn vứt bỏ đi quá nhiều giỏ quýt.

Hãy xác định số thao tác ít nhất mà Cam cần làm nhằm đạt được mục tiêu lợi nhuận tối đa.

Quy ước: Cam có quyền không chọn bán giỏ nào nếu tình hình quá tệ, khi đó tổng lợi nhuận sẽ bằng 0.

Dữ liệu đầu vào (Input)

• Dòng đầu tiên chứa số nguyên ~T~ (1 ≤ ~T~ ≤ 10^5) — số lượng kịch bản (bộ test) cần xử lý.
• Mỗi kịch bản gồm hai dòng:
  • Dòng đầu tiên chứa số nguyên ~N~ (1 ≤ ~N~ ≤ 1000) — tổng số giỏ quýt của Cam.
  • Dòng thứ hai chứa ~N~ số nguyên ~A_1~, ~A_2~, ..., ~A_N~ (-100 ≤ ~A_i~ ≤ 100) — giá trị tương ứng của từng giỏ quýt.

Lưu ý: Tổng ~N~ của tất cả các kịch bản không vượt quá 4 × 10^5.

Kết quả đầu ra (Output)

Với mỗi bộ test, in ra một số nguyên duy nhất — số giỏ quýt ít nhất cần loại bỏ ảnh hưởng để tổng lợi nhuận lớn nhất của một đoạn liên tiếp đạt giá trị lớn nhất có thể.

Ví dụ (Sample)

Input

4
3
-1 -3 -4
3
1 -1 1
5
1 2 -1 -2 4
8
-2 -1 1 3 -1 4 -4 -5

Output

0
1
2
1

Giải thích ví dụ (Note)

• Ở bộ test thứ nhất, mọi phần tử đều âm nên tổng đoạn con lớn nhất luôn bằng 0 (chọn đoạn rỗng), không cần thực hiện thao tác nào.
• Ở bộ test thứ hai, biến đổi ~A_2~ = 0 để dãy trở thành [1, 0, 1], khi đó tổng đoạn con lớn nhất là 2 và chỉ cần 1 thao tác.
• Ở bộ test thứ ba, biến đổi ~A_3~ = 0 và ~A_4~ = 0 để dãy trở thành [1, 2, 0, 0, 4], tổng đoạn con lớn nhất đạt 7 với 2 thao tác.