配点 : $200$ 点

問題文

長さ $N$ の整数列 $A$ があります。

$A$ の 空でない 連続する 部分列であって、その総和が $0$ になるものの個数を求めてください。 ただし、ここで数えるのは 部分列の取り出し方 であることに注意してください。 つまり、ある $2$ つの部分列が列として同じでも、取り出した位置が異なるならば、それらは別々に数えるものとします。

制約

• $1 \leq N \leq 2 \times 10^5$
• $-10^9 \leq A_i \leq 10^9$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$ $A_2$ $...$ $A_N$

出力

$A$ の空でない連続する部分列であって、その総和が $0$ になるものの個数を出力せよ。

6
1 3 -4 2 2 -2

3

空でない連続した部分列であって、その総和が $0$ になるのは、$(1,3,-4)$, $(-4,2,2)$, $(2,-2)$ の $3$ つです。

7
1 -1 1 -1 1 -1 1

12

この例では、列として同じだが取り出す位置の異なる部分列が複数回数えられています。 例えば、$(1,-1)$ は $3$ 回数えられています。

5
1 -2 3 -4 5

0

空でない連続した部分列であって、その総和が $0$ になるものはありません。