Vadim loves decorating the Christmas tree, so he got a beautiful garland as a present. It consists of $n$ light bulbs in a single row. Each bulb has a number from $1$ to $n$ (in arbitrary order), such that all the numbers are distinct. While Vadim was solving problems, his home Carp removed some light bulbs from the garland. Now Vadim wants to put them back on.[Image]

Vadim wants to put all bulb back on the garland. Vadim defines complexity of a garland to be the number of pairs of adjacent bulbs with numbers with different parity (remainder of the division by $2$). For example, the complexity of 1 4 2 3 5 is $2$ and the complexity of 1 3 5 7 6 4 2 is $1$.

No one likes complexity, so Vadim wants to minimize the number of such pairs. Find the way to put all bulbs back on the garland, such that the complexity is as small as possible.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 100$) — the number of light bulbs on the garland.

The second line contains $n$ integers $p_1,\ p_2,\ \ldots,\ p_n$ ($0 \le p_i \le n$) — the number on the $i$-th bulb, or $0$ if it was removed.


-----Output-----

Output a single number — the minimum complexity of the garland.


-----Examples-----
Input
5
0 5 0 2 3

Output
2

Input
7
1 0 0 5 0 0 2

Output
1



-----Note-----

In the first example, one should place light bulbs as 1 5 4 2 3. In that case, the complexity would be equal to 2, because only $(5, 4)$ and $(2, 3)$ are the pairs of adjacent bulbs that have different parity.

In the second case, one of the correct answers is 1 7 3 5 6 4 2.

Difficulty: competition

Starter code:

Solutions:
import sys
readline = sys.stdin.readline

N = int(readline())
S = list(map(int, readline().split()))
S = [0 if s == 0 else 1 if s & 1 else -1 for s in S]

odd = -(-N//2)
even = N//2
for s in S:
    if s:
        if s == 1:
            odd -= 1
        else:
            even -= 1

inf = 10**9
dpe = [[inf]*(odd+1) for _ in range(even+1)]
dpo = [[inf]*(odd+1) for _ in range(even+1)]
dpe[0][0] = 0
dpo[0][0] = 0

for i in range(N):
    dp2e = [[inf]*(odd+1) for _ in range(even+1)]
    dp2o = [[inf]*(odd+1) for _ in range(even+1)]
    s = S[i]
    for e in range(even+1):
        for o in range(odd+1):
            if s == 1:
                dp2o[e][o] = min(dp2o[e][o], dpo[e][o], 1+dpe[e][o])
            elif s == -1:
                dp2e[e][o] = min(dp2e[e][o], dpe[e][o], 1+dpo[e][o])
            else:
                if o < odd:
                    dp2o[e][o+1] = min(dp2o[e][o+1], dpo[e][o], 1+dpe[e][o])
                if e < even:
                    dp2e[e+1][o] = min(dp2e[e+1][o], dpe[e][o], 1+dpo[e][o])
    dpe = [d[:] for d in dp2e]
    dpo = [d[:] for d in dp2o]

print(min(dpe[even][odd], dpo[even][odd]))

n = int(input())
a = list(map(int, input().split()))
INF = 10**5

dp = [[[INF]*(n+1) for i in range(n+1)] for i in range(2)]
dp[0][0][0] = 0
dp[1][0][0] = 0

for i in range(n):
    if a[i] != 0:
        parity = a[i] % 2
        if parity % 2 == 0:
            for j in range(n+1):
                dp[0][i+1][j] = min(dp[0][i][j], dp[0][i+1][j])
                dp[0][i+1][j] = min(dp[1][i][j] + 1, dp[0][i+1][j])
        if parity % 2 == 1:
            for j in range(n):
                dp[1][i+1][j+1] = min(dp[1][i][j], dp[1][i+1][j+1])
                dp[1][i+1][j+1] = min(dp[0][i][j] + 1, dp[1][i+1][j+1])
    else:
        for j in range(n+1):
            dp[0][i+1][j] = min(dp[0][i][j], dp[0][i+1][j])
            dp[0][i+1][j] = min(dp[1][i][j] + 1, dp[0][i+1][j])
        for j in range(n):
            dp[1][i+1][j+1] = min(dp[1][i][j], dp[1][i+1][j+1])
            dp[1][i+1][j+1] = min(dp[0][i][j] + 1, dp[1][i+1][j+1])

odd_cnt = (n+1) // 2
even_cnt = n // 2

print(min(dp[1][n][odd_cnt], dp[0][n][odd_cnt]))


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

n = int(input())
p = list(map(int, input().split()))
odd = (n+1)//2
even = n-odd
for i in p:
    if i:
        if i%2 == 0:
            even -= 1
        else:
            odd -= 1

if even == 0:
    p = [i if i else 1 for i in p]
if odd*even == 0:
    ans = 0
    prev = p[0]
    for pi in p:
        ans += (pi+prev)%2
        prev = pi
    print(ans)
    return

DP = [[float("inf")]*(even+1) for i in range(2)]
for i in range(n):
    nxt = [[float("inf")]*(even+1) for i in range(2)]
    if i == 0:
        if p[i]:
            if p[i]%2 == 0:
                nxt[0][0] = 0
            else:
                nxt[1][0] = 0
        else:
            nxt[0][1] = 0
            nxt[1][0] = 0
    else:
        if p[i]:
            if p[i]%2 == 0:
                for j in range(even+1):
                    nxt[0][j] = min(DP[0][j], DP[1][j]+1)
            else:
                for j in range(even+1):
                    nxt[1][j] = min(DP[0][j]+1, DP[1][j])
        else:
            for j in range(1, even+1):
                nxt[0][j] = min(DP[0][j-1], DP[1][j-1]+1)
            for j in range(even+1):
                nxt[1][j] = min(DP[0][j]+1, DP[1][j])
    DP = nxt
print(min(DP[0][-1], DP[1][-1]))



import sys

inf = 2 ** 30

def solution(a):
    n = len(a)
    m = ((n + 1) >> 1) - sum([v & 1 for v in a])
    f = [[[inf for k in range(2)] for j in range(m +1)] for i in range(n + 1)]
    f[0][0][0], f[0][0][1] = 0, 0
    for i in range(n):
        for j in range(min(m, i) + 1):
            for k in range(2):
                #sys.stderr.write('f[%d][%d][%d] = %d\n' % (i, j, k, f[i][j][k]));
                # fixed
                if a[i] != 0:
                    t = a[i] & 1 
                    w = 1 if t != k else 0
                    f[i + 1][j][t] = min(f[i][j][k] + w, f[i + 1][j][t])
                    continue
                # +1
                if j < m:
                    w = 1 if k != 1 else 0
                    f[i + 1][j + 1][1] = min(f[i][j][k] + w, f[i + 1][j + 1][1])
                # +0
                w = 1 if k != 0 else 0
                f[i + 1][j][0] = min(f[i][j][k] + w, f[i + 1][j][0])
    return min(f[n][m][0], f[n][m][1])

def main():
    while True:
        try:
            n = int(input().strip())
            a = [int(i) for i in input().strip().split()]
            sys.stdout.write('%d\n' % solution(a))
        except ValueError:
            continue
        except EOFError:
            break

def __starting_point():
    main()
__starting_point()