Problem Description

Author: eedwang

眾所周知雪滴大大最近出了一題讓大家都看不下去的題目 所以我也要來出一題讓他看不下去的題目 例如 我們要先加入

一張雪滴的帥圖 然後我們要讓雪滴直播 所以我們來玩主播雪滴過度依賴

遊戲內容是這樣的

對於每一筆測資 - 給你一個數字N (2 ≤ N ≤ 10⁵)代表雪滴再來N天直播粉絲變動量p_i (1 ≤ p_i ≤ 10⁶)(如果有直播或休息) 每天雪滴都有三種選擇 1.直播唱歌 -- 新粉絲數量上漲p[i] ; 休息量-1 2.直播吃豆花(因為雪滴在段考前一天問我們要不要看他直播吃豆花) -- 新粉絲數量維持不變 ; 休息量不變 3.休息 -- 新粉絲數量下降p[i] ; 休息量+1; 休息量需時刻≥0 (初始為0

求雪滴最後能有多多少個新粉絲 (相對一開始的量 不用管原本多少)

Input Format

第一行t代表t筆測資 (1≤t≤1000)

對於每筆測資:

給一個N代表N天直播 再來一行給N個數字代表如果雪滴直播唱歌或休息會增加或減少的新粉絲數

note : ΣN < 2e6

Output Format

每一筆測資雪滴最多多幾個新粉絲

2
9
10 5 4 7 9 12 6 2 10
20
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4

20
41

Hint

對於第一筆測資 在第2,3天休息 之後在第5,6天直播唱歌 第8天再休息 第9天直播唱歌  // (-4) + (-5) + (9) + (12) + (-2) + (10) = 20