問題文

数列の 'たぴさ' を、その数列の 連続する 長さ 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 点が与えられる。

入力例 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