AT_qupc2018_e Treeone

[problemUrl]: https://atcoder.jp/contests/qupc2018/tasks/qupc2018_e 数列の 'たぴさ' を、その数列の **連続する** 長さ $ 1 $ 以上の部分列のうち、要素の総和が $ 0 $ であるものの個数と定義します。 部分列の中身が同じでも、位置が異なれば別のものとして数えることとします。 長さ $ N $ の数列 $ A_1,\ A_2,\ ...,\ A_N $ が与えられます。このうち $ 1 $ つの要素を好きな整数値に変更できるとき、数列の 'たぴさ' の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 点が与えられる。 ### Sample Explanation 1 例えば $ A_2 $ を $ 1 $ に変更すると、総和が $ 0 $ である部分列は $ [1,1] $, $ [3,3] $, $ [4,4] $, $ [3,4] $ の $ 4 $ つとなりこれが最小です。