← 返回题目列表

AtCoder · qupc2018_e

E. 树一

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

配点 : 500 点

問題文

数列的 '长度' 为,该数列中 连续的 长度 小于或等于 1 以上的子列中,元素的总和为 0 的数量。即使子列的内容相同,只要位置不同也作为不同的子列计数。

长度 小于或等于 N 序列 使用 A_1, A_2, ..., A_N 已给出。这其中 1 个元素可以更改为任意整数值时,请求出数列 '长度' 的最小值。

制約

  • 1 \leq N \leq 2 \times 10^5
  • |A_i| \leq 10^9
  • 所有输入均为整数

部分点

  • N \leq 5000 的数据集,40 点。 如果您正确回答了所有满足

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 ... A_N

出力

1 请在一行中输出答案。


入力例 1

4
0 0 0 0

出力例 1

4

例如 第 A_2 该值应乘以 1 改变为后,总和为 0 的子列有 [1,1], [3,3], [4,4], [3,4] 可以得到第 4 个,这是最小值。


入力例 2

6
1 -1 -1 2 -2 0

出力例 2

2