AT_ndpc2026_k 加算と減算

You are given an integer sequence $ A = (A_1, A_2, \dots, A_N) $ of length $ N $ . You also have an integer $ x $ , which is initially $ 0 $ . You will perform the following $ N $ operations: - For $ i = 1, 2, \dots, N $ , choose exactly one of the following three operations: - Replace $ x $ with $ x + A_i $ . - Replace $ x $ with $ \vert x - A_i \vert $ . - Do nothing. Find the number of possible values of $ x $ after all $ N $ operations are completed.

The input is given from standard input in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

Print the number of possible values of $ x $ after all $ N $ operations are completed.

### Partial Score This problem has partial scoring. - If you solve the dataset with $ \displaystyle 1 \leq \sum_{i=1}^N A_i \leq 5 \times 10^5 $ , you will get $ 4 $ points. ### Sample Explanation 1 For example, you can obtain $ x = 9 $ by performing the following operations: - Initially, $ x = 0 $ . - At $ i = 1 $ , replace $ x $ with $ \vert x - A_i \vert = \vert 0 - 2 \vert = 2 $ . - At $ i = 2 $ , replace $ x $ with $ x + A_i = 2 + 7 = 9 $ . - At $ i = 3 $ , do nothing. ### 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 $ - All input values are integers