You are given a circular ring of
N magical orbs, indexed from
0 to
N-1. Each orb is in one of two states: Active (1) or Inert (0).
You can perform a Toggle operation on any orb
i. When you toggle orb
i, the states of the following three orbs are flipped (from 0 to 1, or 1 to 0):
Orb (i-1) \pmod N,
Orb i
Orb (i+1) \pmod N
Your goal is to make all orbs Inert (0) using the minimum number of toggle operations.
Input
The first line contains an integer N (3 \le N \le 10^5), the number of orbs.
The second line contains a string of N characters consisting of '0' and '1', representing the initial states of the orbs.
Output
Print a single integer: the minimum number of toggles required to make all orbs '0'.
If it is impossible to make all orbs '0', print -1.
Examples
| standard input | standard output |
|---|
| 3
000
| 0
|
| 3
111
| 1
|