AT_ndpc2026_k.Addition and Subtraction

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.

给你一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \dots, A_N)$。
你还拥有一个整数 $x$，其初始值为 $0$。

你将执行以下 $N$ 次操作：

• 对于 $i = 1, 2, \dots, N$，从以下三种操作中恰好选择一种：
  • 将 $x$ 替换为 $x + A_i$；
  • 将 $x$ 替换为 $\vert x - A_i \vert$；
  • 不进行任何操作。

求所有 $N$ 次操作完成后，$x$ 可能取到的不同值的个数。

The input is given from standard input in the following format:

$N$
$A_1$ $A_2$ $\dots$ $A_N$

输入从标准输入中按以下格式给出：

$N$
$A_1$ $A_2$ $\dots$ $A_N$

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

输出完成所有 $N$ 次操作后 $x$ 的可能取值个数。

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 1 Explanation:
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

部分得分

本题采用部分得分制。

• 若你解决了满足 $\displaystyle 1 \leq \sum_{i=1}^N A_i \leq 5 \times 10^5$ 的数据集，则可获得 $4$ 分。

样例 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$ 时，不进行任何操作。

约束条件

• $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$
• 所有输入值均为整数