故障机器人

题目描述

数轴上有一个机器人，初始时位于坐标 $0$。高桥还有一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$。

高桥按顺序执行以下步骤：

1. 选择 至多 $1$ 个 $A$ 中的元素并翻转其符号。也就是说，选择 $0$ 个或 $1$ 个下标 $i$（$1 \le i \le N$），把 $A_i$ 替换为 $-A_i$。
2. 启动机器人。启动后，机器人进行 $N$ 次移动。第 $i$ 次移动（$1 \le i \le N$）中，设它当前位于坐标 $x$，则它沿直线移动到坐标 $x+A_i$。

高桥希望让机器人经过的整数坐标数量尽可能多。请求出在最优操作下，机器人经过的整数坐标数量的最大值。

这里，机器人的移动是连续的。当一次移动把机器人从坐标 $S$ 带到坐标 $T$ 时，认为它经过了 $S$ 与 $T$ 之间（含两端）的所有整数坐标。

输入格式

输入第一行为一个整数 $N$。

第二行为 $N$ 个整数 $A_1,A_2,\ldots,A_N$，相邻两个数之间用一个空格隔开。

输出格式

输出一行一个整数，表示答案。

3
-2 3 -2

8

样例 1 解释

最初 $A=(-2,3,-2)$。如果翻转 $A_2$ 的符号，则 $A=(-2,-3,-2)$。机器人依次经过：

• 第 $1$ 次移动：$0 \to -2$，经过 $-2,-1,0$；
• 第 $2$ 次移动：$-2 \to -5$，经过 $-5,-4,-3,-2$；
• 第 $3$ 次移动：$-5 \to -7$，经过 $-7,-6,-5$。

于是机器人经过的整数坐标为 $-7,-6,-5,-4,-3,-2,-1,0$，共 $8$ 个。可以证明这是最大值。

注意，如果不翻转任何元素，机器人会经过 $0 \to -2 \to 1 \to -1$，只经过 $-2,-1,0,1$ 共 $4$ 个整数坐标。

2
2 3

6

样例 2 解释

不翻转任何元素时，机器人经过 $0 \to 2 \to 5$，经过 $0,1,2,3,4,5$ 共 $6$ 个整数坐标，这就是最大值。

数据范围

对于所有测试数据，保证：

• $1 \le N \le 2 \times 10^5$；
• $-10^9 \le A_i \le 10^9$；
• $A_i \neq 0$；
• 所有输入值均为整数。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。