Server Time:

User's AC Ratio in this contest

11.1% (2/18)

Submission's AC Ratio in this contest

3.6% (2/55)

Description

在 22 世紀,哆啦 A 夢是日本警視廳的警視總監,他奉命要調查在太平洋第 7 島鏈上面的勢力,進行武力分析。

哆啦 A 夢派出了小哆啦去調查島鏈上面的小島,這個島鏈上共有 $N$ 個小島,並且對每個小島進行武力分析,得知每個小島的武力值。

這些小島分成兩種派系,一派是支持大雄、一派是支持胖虎,哆啦 A 夢為了保護大雄避免胖虎的欺負,所以想先分析島鏈上有多少個區間,火拼時大雄會輸。

區間火拼:
則計算區間中大雄派的武力值總和與胖虎派武力值總和,若胖虎派武力值總和大於大雄派武力值總和則大雄派輸。

「我不在的時候你能夠好好照顧自己嗎?」哆啦 A 夢邊生氣邊流淚地問大雄。

Input Format

每筆測資只有一組資料
第一行為一個正整數 $N$ ($1 \leq N \leq 2 \cdot10^5$),代表島鏈上面的小島數量。
第二行共有 $N$ 個整數 $a_i$ ($1 \leq |a_i| \leq 10^5$),$\lvert a_i\rvert$ 為小島的武力值,當 $a_i > 0$ 則為大雄派 ,反之則為胖虎派。

Output Format

輸出一個整數,代表島鏈上有多少個區間,火拼時大雄派會輸。

Sample Input 1

5
3 4 5 6 7

Sample Output 1

0

Sample Input 2

5
1021 -5009 1516 -8002 -6311

Sample Output 2

13

Hints

在第一個範例中,小島都是支持大雄,所以大雄沒有輸。
在第二個範例中,共有 13 個區間大雄會輸,分別為:
$[2, 2]$, $[4, 4]$, $[5, 5]$,
$[1, 2]$, $[2, 3]$, $[3, 4]$, $[4, 5]$,
$[1, 3]$, $[2, 4]$, $[3, 5]$,
$[1, 4]$, $[2, 5]$,
$[1, 5]$
以區間 $[1, 4]$ 為例,支持大雄的武力值總和為 $1021+1516=2537$、支持胖虎的武力值總和為 $5009+8002=13011$,因為 $2537 < 13011$,所以這個區間大雄輸。

Problem Source

reference: NHDK Moon Festival Ten Point Round 2021

Subtasks

No. Testdata Range Constraints Score
1 0~4 $N \leq$ $10$ 0
2 0~9 無特別限制 100

Testdata and Limits

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