問題文

ある長さ M の整数列 B は、以下の条件を満たすときいい数列 と呼ばれます。

• 1 \leq i \lt j \lt M かつ |B_i-B_{i+1}|=|B_j-B_{j+1}| を満たす整数対 (i,j) が存在しない。

ペンギンくんの目標は、与えられる長さ N の整数列 A に対して以下の操作を 0 回以上任意の回数繰り返すことで、A をいい数列 にすることです。

• 1 \leq l \leq r \leq N を満たす整数対 (l,r) を選び、A_l,A_{l+1},\ldots,A_r をそれぞれ -1 倍する。

ペンギンくんの目標が達成可能かを判定し、可能なら必要な操作回数の最小値を求めてください。

制約

• 3 \leq N \leq 10^5
• -10^9 \leq A_i \leq 10^9\ (1 \leq i \leq N)
• 入力は全て整数

入力例 1

4
1 3 0 2

出力例 1

1

例えば (l,r)=(2,3) として一度だけ操作を行うとよいです。

入力例 2

4
-2 1 -4 8

出力例 2

0

ペンギンくんの目標は既に達成されています。

入力例 3

4
1 1 1 1

出力例 3

-1

ペンギンくんは目標を達成することができません。

入力例 4

10
-7 4 -8 6 10 3 4 -9 4 7

出力例 4

1

原案: penguinman