题目描述

给定一个长度为 $N$ 的整数序列

你持有一个整数 $x$，初始时 $x=0$。接下来依次对 $i=1,2,\ldots,N$ 执行操作，每次从以下三种操作中任选一种：

• 将 $x$ 替换为 $x+A_i$；
• 将 $x$ 替换为 $|x-A_i|$；
• 什么也不做。

求完成全部 $N$ 次操作后，$x$ 可能取得的不同值的数量。

限制条件

• $1\le N\le 5\times 10^5$
• $1\le A_i\le 2\times 10^6$
• $1\le \sum_{i=1}^{N}A_i\le 2\times 10^6$
• 所有输入均为整数。

输入

N
A_1 A_2 ... A_N

输出

输出完成所有操作后 $x$ 可能取得的不同值的数量。

样例输入 1

3
2 7 5

样例输出 1

10

例如，可以通过以下操作得到 $x=9$：

• 初始时 $x=0$；
• $i=1$ 时，执行 $x\leftarrow|x-A_1|=|0-2|=2$；
• $i=2$ 时，执行 $x\leftarrow x+A_2=2+7=9$；
• $i=3$ 时，什么也不做。

样例输入 2

10
49 85 36 30 71 65 38 45 73 27

样例输出 2

454