题目描述

有一个长度为 $N$ 的整数序列 $A$。

请你求出 $A$ 的所有非空、连续子序列中，总和为 $0$ 的子序列的个数。需要注意的是，这里统计的是子序列的选取方式。也就是说，即使有两个子序列内容相同，只要它们在序列中的位置不同，也要分别计数。

输入格式

输入以如下格式从标准输入中给出。

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

输出格式

输出 $A$ 的所有非空连续子序列中，总和为 $0$ 的子序列的个数。

样例 1

输入

6
1 3 -4 2 2 -2

输出

3

样例 2

输入

7
1 -1 1 -1 1 -1 1

输出

12

样例 3

输入

5
1 -2 3 -4 5

输出

0

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $-10^9 \leq A_i \leq 10^9$
• 输入均为整数。

样例解释 1

所有非空连续子序列中，总和为 $0$ 的有 $3$ 个，分别是 $(1,3,-4)$、$(-4,2,2)$、$(2,-2)$。

样例解释 2

在这个例子中，虽然有些子序列内容相同，但由于选取的位置不同，会被多次计数。例如，$(1,-1)$ 被计数了 $3$ 次。

样例解释 3

没有任何非空连续子序列的总和为 $0$。

由 ChatGPT 4.1 翻译