Problem Statement

In the room where W lives, $N$ stuffed animals are lined up in a row.

There are $3$ types of stuffed animals: carnivores, herbivores, and birds.

The initial state of the row of stuffed animals is represented by a sequence $A$ of length $N$.

$A_i$ being $0,1,2$ means that the $i$-th stuffed animal from the left in the row is a carnivore, a herbivore, or a bird, respectively.

W calls a row of stuffed animals a safe row of stuffed animals if it satisfies the following condition.

• No pair of a carnivore and a herbivore is adjacent.

W wants to make the row a safe row of stuffed animals by repeating the following operation any number of times, $0$ or more.

• Choose $1$ carnivore and one herbivore, and swap their positions.

Determine whether W can obtain a safe row of stuffed animals, and if it is possible, find the minimum number of operations required.

Input

$N$
$A_1\ A_2\ ... A_N$

• All inputs are integers.
• $2 \le N \le 5000$
• $0 \le A_i \le 2$
• $A_i$ being $0,1,2$ means that the $i$-th stuffed animal from the left in the row is a carnivore, a herbivore, or a bird, respectively.

Output

If the row cannot be made a safe row of stuffed animals no matter how many operations are performed, print $-1$.

Otherwise, print the minimum number of operations required to make it a safe row of stuffed animals.

Print a newline at the end.

Sample

3
2 0 1

-1

5
0 0 2 2 0

0

15
0 0 1 2 0 1 0 2 0 1 1 2 1 0 1

2