E - Treeone

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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_21 に変更すると、総和が 0 である部分列は [1,1], [3,3], [4,4], [3,4]4 つとなりこれが最小です。


入力例 2

6
1 -1 -1 2 -2 0

出力例 2

2