Problem Description

An integer sequence $ B $ of length $ M $ is called a good sequence if it satisfies the following condition:

• There does not exist an integer pair $ (i,j) $ such that $1 \leq i < j < M$ and $ |B_i - B_{i+1}| = |B_j - B_{j+1}| $.

Penguin's goal is to transform a given integer sequence $ A $ of length $ N $ into a good sequence by performing the following operation any number of times (including zero):

• Choose an integer pair $ (l,r) $ such that $1 \leq l \leq r \leq N$, and multiply each of $A_l, A_{l+1}, \ldots, A_r$ by $ -1 $.

Determine if Penguin's goal is achievable and, if so, find the minimum number of operations required.

Input Format

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

$ N $ $ A_1 $ $ A_2 $ $\ldots$ $ A_N $

Output Format

If Penguin's goal is achievable, output the minimum number of operations; otherwise, output -1.

Sample Input and Output

Sample Input #1

4
1 3 0 2

Sample Output #1

1

Sample Input #2

4
-2 1 -4 8

Sample Output #2

0

Sample Input #3

4
1 1 1 1

Sample Output #3

-1

Sample Input #4

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

Sample Output #4

1

Notes/Hints

Constraints

• $3 \leq N \leq 10^5$
• $-10^9 \leq A_i \leq 10^9 \ (1 \leq i \leq N)$
• All inputs are integers

Sample Explanation 1

For example, performing the operation once with $ (l,r)=(2,3) $ is good.

Sample Explanation 2

Penguin's goal is already achieved.

Sample Explanation 3

Penguin cannot achieve his goal.

Sample Explanation 4

Original idea: penguinman

见题面 Input 部分

见题面 Output 部分