AT_qupc2018_e.Treeone

我们定义一个数列的“たぴさ”是数列中所有连续且长度至少为 $1$ 的子序列中，总和为 $0$ 的子序列数量。即使子序列的数值相同，只要位置不同，它们就被视作不同的子序列。

现在给定一个长度为 $N$ 的数列 $A_1, A_2, \ldots, A_N$，你可以选择将其中一个元素更改为任意整数。请计算经过修改后，数列的“たぴさ”可以达到的最小值。

输入以如下形式给出：

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

请输出修改后的数列的最小“たぴさ”的值。

约束

• $1 \leq N \leq 2 \times 10^5$
• $|A_i| \leq 10^9$
• 所有输入都是整数

部分分数

• 如果能够正确解决 $N \leq 5000$ 的情况，将获得 $40$ 分。

示例解释

例如，如果将 $A_2$ 修改为 $1$，总和为 $0$ 的子序列将变为 $[1, 1], [3, 3], [4, 4], [3, 4]$，共 $4$ 个，这是可能实现的最小数量。

本翻译由 AI 自动生成