/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
数直線上にロボットがいます。はじめ、ロボットは座標 0 にいます。 また、高橋君は長さ N の整数列 A=(A_1,A_2,\ldots,A_N) を持っています。
高橋君は次の操作を行います。
-
A の要素を 高々 1 つ 選び、その符号を反転させる。すなわち、1\leq i\leq N をみたす i を 0 または 1 つ選び、A_i を -A_i に書き換える。
-
ロボットを起動する。ロボットは起動後、N 回の行動を行う。i 回目 (1\leq i\leq N) の行動では、現在の座標を x として、座標 x+A_i へ直線的に移動する。
高橋君はロボットが一度以上通る整数座標の個数をなるべく多くしたいです。
高橋君が最適に行動したときの、「ロボットが一度以上通る整数座標の個数」としてあり得る最大の値を求めてください。
なお、ロボットは連続的に移動するものとし、ある移動で座標 S から T まで移動したとき、S\leq T ならば S 以上 T 以下の任意の整数座標、S>T ならば T 以上 S 以下の任意の整数座標を通ったとみなします。
制約
- 1 \leq N \leq 2\times 10^5
- -10^9 \leq A_i \leq 10^9
- A_i\neq 0
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \cdots A_N
出力
高橋君が最適に行動したとき、ロボットが一度以上通る整数座標の個数としてあり得る最大の値を出力せよ。
入力例 1
3 -2 3 -2
出力例 1
8
最初、A=(-2,3,-2) です。高橋君が A_2 の符号を反転させると、A=(-2,-3,-2) となります。 このとき、ロボットは以下のように動きます。
- ロボットは 1 回目の移動で、0 から -2 へ動きます。この移動でロボットが通る整数座標は -2,-1,0 です。
- ロボットは 2 回目の移動で、-2 から -5 へ動きます。この移動でロボットが通る整数座標は -5,-4,-3,-2 です。
- ロボットは 3 回目の移動で、-5 から -7 へ動きます。この移動でロボットが通る整数座標は -7,-6,-5 です。
よって、ロボットが一度以上通る整数座標は -7,-6,-5,-4,-3,-2,-1,0 の 8 つとなり、このとき個数が最大となります。よって、8 を出力します。
なお、高橋君がどの要素の符号も反転させなかったとすると、ロボットは 0\to -2\to 1\to -1 と動き、一度以上通る整数座標は -2,-1,0,1 の 4 つとなります。
入力例 2
2 2 3
出力例 2
6
A の要素を書き換えないとき、ロボットは 0\to 2\to 5 と動き、一度以上通る整数座標の個数は 0,1,2,3,4,5 の 6 個です。
このときが最大であるため、 6 を出力します。
Score : 400 points
Problem Statement
There is a robot on a number line. Initially, the robot is at coordinate 0. Also, Takahashi has an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.
Takahashi performs the following steps in order.
-
Choose at most 1 element of A and flip its sign. That is, choose 0 or 1 index i satisfying 1\leq i\leq N, and replace A_i with -A_i.
-
Start the robot. After starting, the robot makes N moves. In the i-th move (1\leq i\leq N), letting x be its current coordinate, the robot moves in a straight line to coordinate x+A_i.
Takahashi wants to maximize the number of integer coordinates that the robot passes through at least once.
Find the maximum possible value of "the number of integer coordinates that the robot passes through at least once" when Takahashi acts optimally.
Here, the robot moves continuously. When a move takes the robot from coordinate S to coordinate T, it is considered to have passed through every integer coordinate between S and T, inclusive.
Constraints
- 1 \leq N \leq 2\times 10^5
- -10^9 \leq A_i \leq 10^9
- A_i\neq 0
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
Print the maximum possible value of the number of integer coordinates that the robot passes through at least once when Takahashi acts optimally.
Sample Input 1
3 -2 3 -2
Sample Output 1
8
Initially, A=(-2,3,-2). If Takahashi flips the sign of A_2, then A=(-2,-3,-2). In this case, the robot moves as follows.
- In its 1-st move, the robot moves from 0 to -2. The integer coordinates it passes through in this move are -2,-1,0.
- In its 2-nd move, the robot moves from -2 to -5. The integer coordinates it passes through in this move are -5,-4,-3,-2.
- In its 3-rd move, the robot moves from -5 to -7. The integer coordinates it passes through in this move are -7,-6,-5.
Thus, the integer coordinates the robot passes through at least once are the 8 coordinates -7,-6,-5,-4,-3,-2,-1,0, and this is the maximum possible count, so print 8.
Note that if Takahashi did not flip the sign of any element, the robot would move as 0\to -2\to 1\to -1, and the integer coordinates it passes through at least once would be the 4 coordinates -2,-1,0,1.
Sample Input 2
2 2 3
Sample Output 2
6
If no element of A is changed, the robot moves as 0\to 2\to 5, and the integer coordinates it passes through at least once are the 6 coordinates 0,1,2,3,4,5.
This is the maximum possible count, so print 6.