TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

66.7% (4/6)

Submission's AC Ratio

43.8% (7/16)

Tags

Description

你成功的過了橋了,帶著你撿到的小蘿莉,來到了一個暫時安全的躲藏處了。
「喔膩醬,我好害怕喔,他們到了晚上會不會又來襲擊我們呢?」
可惜你現在只被蘿莉的叫聲所迷倒了。
「再...再叫一次...」
「喔膩醬...」
「啊...我受不了了...喔啊喔...」
你沉醉於被叫哥哥的情境中,不知不覺就天黑了。
「嗚...」你身旁的祈都快哭出來了。
「唉...什麼時候天黑了?」你突然發現祈說的沒錯,夜晚被襲擊的機率還真的不低。此時你觀察了一下四周,你發現這個暫時的避難所似乎有別人曾經來過,還做了許多排的陷阱陣可以拖延殭屍襲來的速度。
「何不利用這些陷阱?」你這樣想到,你數了一下某一排的陷阱陣恰好有N個陷阱,而每個陷阱都有一個防禦度ai代表他可以幫你拖延殭屍的能力,不過因為這些陷阱有些已經損壞了,因此這個值有好有壞。而假設這一排陷阱陣的防禦度分別為a_1 ,a_2 ,...,a_n,如果存在一段a_1 ,a_2 ,...,a_i 的總和≤0那這個陷阱陣就很有可能無法有效的抵擋殭屍來襲,我們就說是「不安全」的,反之如果不存在,我們就說這個陷阱陣是「安全」的。
「該怎麼做呢?」你想到了兩種方案
1.花一分鐘的時間修復一個陷阱,讓陷阱的防禦度增加1
2.花一分鐘的把最後面的陷阱搬到最前面去
已經天黑了,殭屍很有可能隨時會襲來,你最少要花多少時間才能讓每排陷阱陣變成安全的呢?

Input Format

第一行有一個正整數T代表有幾排陷阱陣
接下來有一個正整數N代表這排陷阱陣中有多少陷阱
之後有N個整數a_i 代表排在第i的陷阱的防禦度。

Output Format

輸出N行
每一行有一個整數代表讓這個陷阱陣變成安全的需要多少時間

Sample Input 1

3
7
-1 2 3 -4 5 -6 2
5
-3 0 0 0 2
7
0 1 1 1 1 1 1

Sample Output 1

1
3
1

Hints

所有測資 : |a_i |<107

測資組A : T≤5,N≤1000
測資組B : T≤15,N≤105
測資組C : T≤20,N≤106

Problem Source

Step5

Subtasks

No. Testdata Range Score
1 0~1 30
2 2~6 40
3 7~9 30

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 2
3 1000 65536 262144 2
4 1000 65536 262144 2
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 3
8 1000 65536 262144 3
9 2000 65536 262144 3