User's AC Ratio

60.0% (9/15)

Submission's AC Ratio

24.7% (22/89)

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

Sample Input 2

5
1021 -5009 1516 -8002 -6311

Sample Output 2

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

Submit

Status

Ranklist

98 . 每個人都需要一個機器貓朋友