← 返回题目列表

Codeforces · 1426/D

D. 非零段

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

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$$$ 的子段,因此您无需执行任何操作。