電腦配件

在常盤台中學的宿舍中，：白井しらい黑子くろこ以「合法的手段」讓美琴的前任室友離開讓自己搬進「姐姐大人」的房間中。今天剛好是黑子搬進宿舍的第一個月紀念日，因此她特別訂購了「電腦配件」要與「姐姐大人」共度這浪漫的一天。

不過由於今日巧遇周末，貨運公司基於一例一修的政策暫停配送所有的商品，因此黑子需要自己去附近的服務中心領取「電腦配件」。身為常盤台中學的學生，白井黑子是LV4的空間移動能力者，可以把自己連同所要攜帶的東西瞬間移動到設定的位置去，不過移動的距離受到當下空間的能量所影響。若在一次跳躍的過程要能夠穿越$K$個能量體，依序為：$a_1,a_2,a_3\cdots a_K$，那黑子要穿越第$N$個能量體時，要使該能量體$a_N$與已穿越的所有能量體的總和不為負數，否則黑子的身體會被外界力量所吞噬。

而如果一個能量體序列$a_1,a_2,a_3\cdots a_K$是穿越安全序列，表示黑子可以安全的由第一個能量體穿越到第$K$個能量體，並且也能從第$K$個能量體穿越到第一個能量體。如果知道了從黑子的位置到服務中心中間依序有$N$個能量體，能幫黑子計算當中最長的穿越安全序列有多長嗎？

InputFile

只有一筆測資。第一行有一個數字$N$，表示能量體序列的長度。接下來下一行有$N$個整數$a_i$以空白隔開，依序表示每個能量體的強度。

$0< N \leq 10^6$
$\sum{N} \leq 10^7$
$\left |a_i\right |<10^9$

OutputFile

對於每一個詢問輸出一行，為最長的穿越安全序列長度。

範例輸入1

10
-6 -4 -1 0 5 1 9 -8 -3 4

範例輸出1

範例輸入2

10
-6 -4 -1 0 5 1 9 -8 -3 4

範例輸出2

提示

第一筆測資中，$0~5~1~9$是最長的穿越安全序列，第二筆測資全部就是最長的穿越安全序列。

危險的黑子

Judge Setting

run-time limit: 500 ms
memory limit: 67108864 byte
測資數量: 0