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$$$。