AT_ndpc2026_k 加算と減算

長さ $ N $ の整数列 $ A = (A_1, A_2, \dots, A_N) $ があります。 また、あなたは整数 $ x $ を持っています。はじめ $ x=0 $ です。 あなたは次の $ N $ 回の操作を行います。 - $ i = 1, 2, \dots, N $ の順に、次の $ 3 $ 種類の操作のうちどれか $ 1 $ つを行う。 - $ x $ を $ x + A_i $ に置き換える。 - $ x $ を $ \vert x - A_i \vert $ に置き換える。 - 何もしない。 $ N $ 回の操作が終了した時点での $ x $ の値としてあり得るものの個数を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

$ N $ 回の操作が終了した時点での $ x $ の値としてあり得るものの個数を出力せよ。

### 部分点 この問題には部分点が設定されている。 - $ \displaystyle 1 \leq \sum_{i=1}^N A_i \leq 5 \times 10^5 $ であるデータセットに正解した場合、 $ 4 $ 点が与えられる。 ### Sample Explanation 1 例えば次の操作を行うことで操作後の $ x $ を $ 9 $ にすることができます。 - はじめ、 $ x=0 $ である。 - $ i=1 $ の時、 $ x $ を $ \vert x-A_i \vert = \vert 0-2 \vert = 2 $ に置き換える。 - $ i=2 $ の時、 $ x $ を $ x+A_i=2+7=9 $ に置き換える。 - $ i=3 $ の時、何もしない。 ### Constraints - $ 1 \leq N \leq 5 \times 10^5 $ - $ 1 \leq A_i \leq 2 \times 10^6 $ - $ \displaystyle 1 \leq \sum_{i=1}^N A_i \leq 2 \times 10^6 $ - 入力される値は全て整数