Kolya 得到一个整数数组 $$$a_1, a_2, \dots, a_n$$$。该数组可以包含正整数和负整数,但 Kolya 不喜欢 $$$0$$$,因此该数组不包含任何零。
Kolya 不喜欢他的数组的某些子段的总和可以是 $$$0$$$。子段是数组元素的一些连续段。
你必须帮助 Kolya 并更改他的数组,使其不包含任何总和为 $$$0$$$ 的子段。为了达到这个目标,您可以在数组的任何一对相邻元素之间插入任何整数(整数可以是任何整数:正数、负数、$$$0$$$、任何绝对值,甚至是大到无法用大多数标准编程语言表示的整数)。
您的任务是找到必须插入 Kolya 数组中的最小整数数,确保生成的数组不包含任何总和为 $$$0$$$ 的子段。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 200\,000$$$) — Kolya 数组中的元素数量。
输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-10^{9} \le a_i \le 10^{9}, a_i \neq 0$$$) — Kolya 数组的描述。
输出
打印必须插入 Kolya 数组中的最小整数数,确保生成的数组不包含任何总和为 $$$0$$$ 的子段。
示例
输入 #1
4 1 -5 3 2
输出 #1
1
输入 #2
5 4 -2 3 -9 2
输出 #2
0
输入 #3
9 -1 1 -1 1 -1 1 1 -1 -1
输出 #3
6
输入#4
8 16 -5 -11 -15 10 5 4 -4
输出#4
3
注意
考虑第一个例子。只有一个子分段的总和为 $$$0$$$。它从第二个元素开始,到第四个元素结束。插入一个元素就足够了,这样数组就不包含任何总和为零的子段。例如,可以在数组的第二个和第三个元素之间插入整数 $$$1$$$。
第二个示例中没有总和为 $$$0$$$ 的子段,因此您无需执行任何操作。