← 返回题目列表

Codeforces · 1333/C

C. 尤金和一个数组

中文机器翻译题面 查看原题

Eugene 喜欢使用数组。今天他需要你的帮助来解决一项具有挑战性的任务。

数组 $$$c$$$ 是数组 $$$b$$$ 的子数组,如果 $$$c$$$ 可以通过删除开头的几个(可能是零个或全部)元素和末尾的几个(可能是零个或全部)元素从 $$$b$$$ 获得。

如果对于该数组的每个非空子数组,该子数组的元素之和不为零,我们称该非空数组为好数组。例如,数组 $$$[-1, 2, -3]$$$ 很好,因为所有数组 $$$[-1]$$$、$$$[-1, 2]$$$、$$$[-1, 2, -3]$$$、$$$[2]$$$、$$$[2, -3]$$$、$$$[-3]$$$ 都有非零的元素和。然而,数组 $$$[-1, 2, -1, -3]$$$ 不好,因为他的子数组 $$$[-1, 2, -1]$$$ 的元素总和等于 $$$0$$$。

帮助 Eugene 计算给定数组 $$$a$$$ 的非空好子数组的数量。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \times 10^5$$$) — 数组 $$$a$$$ 的长度。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — $$$a$$$ 的元素。

输出

输出一个整数——$$$a$$$ 的好子数组的数量。

示例

输入 #1

3
1 2 -3

输出 #1

5

输入 #2

3
41 -41 41

输出 #2

3

注意

在第一个示例中,以下子数组很好:$$$[1]$$$、$$$[1, 2]$$$、$$$[2]$$$、$$$[2, -3]$$$、$$$[-3]$$$。然而,子数组 $$$[1, 2, -3]$$$ 不好,因为它的子数组 $$$[1, 2, -3]$$$ 的元素总和等于 $$$0$$$。

在第二个示例中,三个大小为 1 的子数组是唯一的好子数组。同时,子数组 $$$[41, -41, 41]$$$ 也不好,因为它的子数组 $$$[41, -41]$$$ 的元素总和等于 $$$0$$$。