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: MEDIUM_HARD
Tags: Dynamic programming

Sorting

Greedy algorithms
Skill types: Dynamic programming

Sorting

Greedy algorithms

Starter code:

Solutions:
def ip():
	n = int(input())
	a = list(map(int, input().split()))
	rem = set([i for i in range(1, n + 1)]) - set(a)
	if n == 1:
		return 0
	o = e = 0
	for i in rem:
		if i % 2 == 0:
			e += 1
		else:
			o += 1
	ct = 0
	i = 0
	while i < len(a) and a[i] == 0:
		i += 1
	if i == len(a):
		return 1
	else:
		startodd = starteven = endodd = endeven = 0
		es = []
		os = []
		if i != 0:
			if a[i] % 2 == 0:
				starteven = i
			else:
				startodd = i
		start = i
		i = len(a) - 1
		end = 0
		while i >= 0 and a[i] == 0:
			i -= 1
			end += 1
		if end != 0:
			if a[i] % 2 == 0:
				endeven = end
			else:
				endodd = end
		end = i
		prev = start
		for i in range(start + 1, end + 1):
			if a[i] == 0:
				continue
			if i - prev > 1:
				if a[i] % 2 == 0 and a[prev] % 2 == 0:
					es.append(i - prev - 1)
				elif a[i] % 2 != 0 and a[prev] % 2 != 0:
					os.append(i - prev - 1)
				else:
					ct += 1
			elif i - prev == 1:
				if a[i] % 2 != a[prev] % 2:
					ct += 1
			prev = i
		os.sort(reverse=True)
		es.sort(reverse=True)
		while os and os[-1] <= o:
			o -= os[-1]
			os.pop()
		if startodd != 0 and o >= startodd:
			o -= startodd
			startodd = 0
		elif startodd != 0:
			os.append(startodd)
		if endodd != 0 and o >= endodd:
			o -= endeven
			endodd = 0
		elif endodd != 0:
			os.append(endodd)
		ct += max(len(os) * 2, 0)
		while es and es[-1] <= e:
			e -= es[-1]
			es.pop()
		if starteven != 0 and e >= starteven:
			e -= starteven
			starteven = 0
		elif starteven != 0:
			es.append(starteven)
		if endeven != 0 and e >= endeven:
			e -= endeven
			endeven = 0
		elif endeven != 0:
			es.append(endeven)
		ct += max(len(es) * 2, 0)
		if startodd != 0 and startodd in os or startodd + o in os:
			ct -= 1
		if starteven != 0 and starteven in es or starteven + e in es:
			ct -= 1
		if endodd != 0 and endodd in os or endodd + o in os:
			ct -= 1
		if endeven != 0 and endeven in es or endeven + e in es:
			ct -= 1
		return ct
print(ip())


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def solve():
	n = mint()
	a = list(mints())
	o_all = 0
	for i in range(1, n + 1, 2):
		o_all += 1
	e_all = 0
	for i in range(2, n + 1, 2):
		e_all += 1
	dp = [None] * n
	for i in range(n):
		z = [None] * (n + 1)
		for j in range(n + 1):
			z[j] = [1000000000.0, 1000000000.0]
		dp[i] = z
	if a[0] == 0:
		dp[0][1][0] = 0
		dp[0][0][1] = 0
	elif a[0] % 2 == 0:
		dp[0][1][0] = 0
	else:
		dp[0][0][1] = 0
	for i in range(0, n - 1):
		for e in range(0, i + 2):
			o = i + 1 - e
			el = e_all - e
			ol = o_all - o
			for jp in range(2):
				for j in range(2):
					if j == 0 and el > 0 or (j == 1 and ol > 0):
						if a[i + 1] == 0:
							dp[i + 1][e + 1 - j][j] = min(dp[i + 1][e + 1 - j][j], dp[i][e][jp] + (jp != j))
						elif a[i + 1] % 2 == j:
							dp[i + 1][e + 1 - j][j] = min(dp[i + 1][e + 1 - j][j], dp[i][e][jp] + (jp != j))
	print(min(dp[n - 1][e_all][0], dp[n - 1][e_all][1]))
solve()


n = int(input())
a = [int(x) for x in input().split()]
(imp, par) = (0, 0)
for i in range(n):
	if a[i] == 0:
		a[i] -= 1
	else:
		a[i] %= 2
		imp += a[i] % 2 == 1
		par += a[i] % 2 == 0
ans = 0
for i in range(n - 1):
	if a[i] != -1 and a[i + 1] != -1 and (a[i] + a[i + 1] == 1):
		ans += 1
(b0, b1, b00, b11, irest) = ([], [], [], [], 0)
if a[0] == -1:
	i = 0
	while i < n:
		if a[i] != -1:
			b0.append(i) if a[i] == 0 else b1.append(i)
			break
		i += 1
if a[-1] == -1:
	i = n - 1
	while i >= 0:
		if a[i] != -1:
			b0.append(n - 1 - i) if a[i] == 0 else b1.append(n - 1 - i)
			break
		i -= 1
lastfill = -1
for i in range(n):
	if a[i] != -1:
		if lastfill != -1 and i - lastfill > 1:
			if a[i] == 0 and a[lastfill] == 0:
				b00.append(i - lastfill - 1)
			elif a[i] == 1 and a[lastfill] == 1:
				b11.append(i - lastfill - 1)
			else:
				irest += 1
		lastfill = i
restpar = n // 2 - par
restimpar = n - n // 2 - imp
b0.sort(reverse=True)
b00.sort(reverse=True)
b1.sort(reverse=True)
b11.sort(reverse=True)
ans += irest
while b00 and b00[-1] <= restpar:
	restpar -= b00.pop()
while b11 and b11[-1] <= restimpar:
	restimpar -= b11.pop()
while b0 and b0[-1] <= restpar:
	restpar -= b0.pop()
while b1 and b1[-1] <= restimpar:
	restimpar -= b1.pop()
ans += len(b0) + len(b1) + 2 * len(b11) + 2 * len(b00)
print(1) if par + imp == 0 and n > 1 else print(ans)


n = int(input())
p = list(map(int, input().split()))
odd = (n + 1) // 2
memo = {}

def best(i, odd_count, last):
	if i == n:
		return 0
	key = (i, odd_count, last)
	if key in memo:
		return memo[key]
	poss = range(2) if p[i] == 0 else [p[i] % 2]
	res = 10 ** 9
	for parity in poss:
		new_odd_count = odd_count - parity
		new_even_count = n - i - odd_count - (parity ^ 1)
		if new_odd_count < 0 or new_even_count < 0:
			continue
		res = min(res, best(i + 1, new_odd_count, parity) + (1 if i > 0 and last != parity else 0))
	memo[key] = res
	return res
print(best(0, odd, 0))


from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
	n = I()
	a = LI()
	s = [1] * (n + 1)
	for i in a:
		s[i] = 0
	odd = 0
	even = 0
	for i in range(1, n + 1, 2):
		odd += s[i]
	for i in range(2, n + 1, 2):
		even += s[i]
	dp = [[[[float('inf')] * 2 for k in range(even + 1)] for i in range(odd + 1)] for j in range(n)]
	if a[0] != 0:
		dp[0][0][0][a[0] & 1] = 0
	else:
		if odd:
			dp[0][1][0][1] = 0
		if even:
			dp[0][0][1][0] = 0
	for i in range(n - 1):
		ni = i + 1
		for j in range(odd + 1):
			for k in range(even + 1):
				if a[ni] != 0:
					for l in range(2):
						nl = a[ni] & 1
						nd = dp[i][j][k][l] + (l ^ nl)
						if dp[ni][j][k][nl] > nd:
							dp[ni][j][k][nl] = nd
				else:
					nj = j + 1
					nk = k
					nl = 1
					if nj <= odd:
						for l in range(2):
							nd = dp[i][j][k][l] + (l ^ nl)
							if dp[ni][nj][nk][nl] > nd:
								dp[ni][nj][nk][nl] = nd
					nj = j
					nk = k + 1
					nl = 0
					if nk <= even:
						for l in range(2):
							nd = dp[i][j][k][l] + (l ^ nl)
							if dp[ni][nj][nk][nl] > nd:
								dp[ni][nj][nk][nl] = nd
	print(min(dp[-1][odd][even]))
	return
solve()


def solve():
	N = int(input())
	P = list(map(int, input().split()))
	if N <= 1:
		return 0
	taken = [False for i in range(N + 1)]
	for i in range(len(P)):
		if P[i] == 0:
			continue
		taken[P[i]] = True
		if P[i] % 2 == 0:
			P[i] = 2
		else:
			P[i] = 1
	num1 = 0
	num2 = 0
	for i in range(1, N + 1):
		if not taken[i]:
			if i % 2 == 0:
				num2 += 1
			else:
				num1 += 1
	if num1 + num2 == N:
		return 1
	ans = 0
	ks1 = []
	ks2 = []
	num01 = 0
	it = 0
	if P[0] == 0:
		while P[it] == 0:
			it += 1
		if P[it] == 1:
			ks1.append((it, 1))
		if P[it] == 2:
			ks2.append((it, 1))
	while it < N:
		if it + 1 == N:
			break
		if P[it + 1] == 0:
			leftit = it
			it += 1
			while it < N and P[it] == 0:
				it += 1
			if it == N:
				if P[leftit] == 1:
					ks1.append((N - leftit - 1, 1))
				if P[leftit] == 2:
					ks2.append((N - leftit - 1, 1))
			elif P[it] == 1 and P[leftit] == 1:
				ks1.append((it - leftit - 1, 2))
			elif P[it] == 2 and P[leftit] == 2:
				ks2.append((it - leftit - 1, 2))
			else:
				num01 += 1
		else:
			if P[it] != P[it + 1]:
				num01 += 1
			it += 1

	def knapsack(items, limit):
		ks = [[0 for _ in range(limit + 1)] for _ in items]
		for i in range(len(items)):
			(weight, price) = items[i]
			for j in range(limit + 1):
				if j == 0:
					continue
				if j >= weight:
					if i == 0:
						ks[i][j] = price
					else:
						take = price + ks[i - 1][j - weight]
						donttake = ks[i - 1][j]
						ks[i][j] = max(take, donttake)
				elif i == 0:
					ks[i][j] = 0
				else:
					ks[i][j] = ks[i - 1][j]
		if len(ks) == 0:
			return 0
		return ks[-1][-1]
	ans += num01
	ans += sum([x[1] for x in ks1])
	ans += sum([x[1] for x in ks2])
	ans -= knapsack(ks1, num1)
	ans -= knapsack(ks2, num2)
	return ans
print(solve())


n = int(input())
z = float('INF')
a = [int(x) for x in input().split()]
dp = [[[[z] * 2 for k in range(n + 1)] for j in range(n + 1)] for i in range(n + 1)]
dp[0][0][0][0] = 0
dp[0][0][0][1] = 0
for i in range(1, n + 1):
	for j in range(n + 1):
		if a[i - 1] & 1:
			dp[i][j][i - j][1] = min(dp[i - 1][j][i - j - 1][0] + 1, dp[i - 1][j][i - j - 1][1])
		elif a[i - 1] == 0:
			dp[i][j][i - j][1] = min(dp[i - 1][j][i - j - 1][0] + 1, dp[i - 1][j][i - j - 1][1])
			dp[i][j][i - j][0] = min(dp[i - 1][j - 1][i - j][0], dp[i - 1][j - 1][i - j][1] + 1)
		else:
			dp[i][j][i - j][0] = min(dp[i - 1][j - 1][i - j][0], dp[i - 1][j - 1][i - j][1] + 1)
e = (n - (n & 1)) // 2
o = (n + (n & 1)) // 2
ans = [dp[n][e][o][0], dp[n][e][o][1]]
if a[n - 1] == 0:
	print(min(ans))
else:
	print(ans[a[n - 1] & 1])


n = int(input())
bulbs = list(map(int, input().split()))
li = []
odds = 0
blanks = 0
for (i, e) in enumerate(bulbs):
	if e != 0:
		if e % 2 == 1:
			li.append((i, 1))
			odds += 1
		else:
			li.append((i, 0))
	else:
		blanks += 1
odds = (n + 1) // 2 - odds
even = blanks - odds
ans = 0
spaces = []
if len(li) > 0 and li[0][0] != 0:
	li = [(-1, li[0][1])] + li
if len(li) > 0 and li[-1][0] != n - 1:
	li = li + [(n, li[-1][1])]
for i in range(len(li) - 1):
	if li[i][1] == li[i + 1][1]:
		temp = (li[i][0] == -1 or li[i + 1][0] == n, li[i + 1][0] - li[i][0] - 1, li[i][1])
	else:
		temp = None
		ans += 1
	if temp is not None and temp[1] > 0:
		spaces.append(temp)
spaces.sort()
for space in spaces:
	if space[2] == 0:
		if even < space[1]:
			ans += 1 if space[0] else 2
		else:
			even -= space[1]
	elif odds < space[1]:
		ans += 1 if space[0] else 2
	else:
		odds -= space[1]
if len(li) == 0:
	ans = min(1, n - 1)
print(ans)


a = int(input())
z = list(map(int, input().split()))
import math
odd = 0
eve = 0
for i in range(len(z)):
	if z[i] % 2 == 1:
		odd += 1
	elif z[i] % 2 == 0 and z[i] > 0:
		eve += 1
odd = a // 2 + a % 2 - odd
eve = a // 2 - eve + a % 2
cnt = 0
dp = [[[math.inf for i in range(2)] for i in range(odd + 2)] for i in range(len(z))]
for i in range(len(z)):
	if i == 0 and z[i] == 0:
		cnt += 1
		dp[i][1][0] = 0
		dp[i][0][1] = 0
		continue
	elif i == 0 and z[i] != 0:
		dp[i][0][1 - z[i] % 2] = 0
		continue
	if z[i] != 0:
		if z[i - 1] != 0:
			for j in range(min(cnt + 1, odd + 1)):
				dp[i][j][1 - z[i] % 2] = dp[i - 1][j][1 - z[i - 1] % 2] + int(z[i] % 2 != z[i - 1] % 2)
		else:
			for j in range(min(cnt + 1, odd + 1)):
				dp[i][j][1 - z[i] % 2] = min(dp[i - 1][j][1 - z[i] % 2], dp[i - 1][j][z[i] % 2] + 1)
	else:
		cnt += 1
		for j in range(min(cnt + 1, odd + 1)):
			if j == 0:
				dp[i][j][1] = min(dp[i - 1][j][0] + 1, dp[i - 1][j][1])
			else:
				dp[i][j][0] = min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1] + 1)
				dp[i][j][1] = min(dp[i - 1][j][1], dp[i - 1][j][0] + 1)
mini = math.inf
mini = min(dp[len(z) - 1][odd][0], dp[len(z) - 1][odd][1])
print(mini)


import sys
n = int(input())
ar = list(map(int, input().split()))
no = set([i for i in range(1, n + 1)])
ars = set(ar)
if 0 in ars:
	ars.remove(0)
dif = no - ars
odds = 0
even = 0
for i in dif:
	if i % 2 == 0:
		even += 1
odds = len(dif) - even
n1 = len(dif)
dp = {}

def gar(i, odds, typ, n1):
	global dp
	if i == n or n == 1:
		return 0
	if (i, odds, typ, n1) in dp:
		return dp[i, odds, typ, n1]
	(val1, val2, val) = (sys.maxsize, sys.maxsize, sys.maxsize)
	if ar[i] == 0 and odds > 0:
		val1 = gar(i + 1, odds - 1, 1, n1 - 1)
		if typ == 0:
			val1 += 1
	if ar[i] == 0 and n1 - odds > 0:
		val2 = gar(i + 1, odds, 0, n1 - 1)
		if typ == 1:
			val2 += 1
	if ar[i] != 0:
		val = 0
		if typ != ar[i] % 2:
			val = gar(i + 1, odds, ar[i] % 2, n1) + 1
		else:
			val = gar(i + 1, odds, ar[i] % 2, n1)
	if val >= sys.maxsize:
		dp[i, odds, typ, n1] = min(val1, val2)
	else:
		dp[i, odds, typ, n1] = val
	return dp[i, odds, typ, n1]
if ar[0] == 0:
	if odds != 0:
		val = min(gar(1, odds, 0, n1 - 1), gar(1, odds - 1, 1, n1))
	else:
		val = gar(1, odds, 0, n1)
elif ar[0] % 2 == 0:
	val = gar(1, odds, 0, n1)
else:
	val = gar(1, odds, 1, n1)
print(val)


def f(mass, a):
	mass.sort()
	prov = True
	for i in range(len(mass)):
		if a >= mass[i]:
			a -= mass[i]
		else:
			prov = False
			break
	if prov:
		return [0, a]
	return [2 * (len(mass) - i), a]
n = int(input())
if n == 1:
	print(0)
else:
	mass = [int(i) for i in input().split()]
	chet = 0
	nechet = 0
	length = 0
	chet_mass = []
	nechet_mass = []
	now = -1
	begin = (0, 0)
	end = (0, 0)
	counter = 0
	for i in range(n):
		if mass[i] == 0:
			length += 1
		elif mass[i] % 2 == 0:
			chet += 1
			if length != 0:
				if now == 0:
					chet_mass.append(length)
				elif now == -1:
					begin = (length, 0)
				else:
					counter += 1
			elif now == 1:
				counter += 1
			now = 0
			length = 0
		else:
			nechet += 1
			if length != 0:
				if now == 1:
					nechet_mass.append(length)
				elif now == -1:
					begin = (length, 1)
				else:
					counter += 1
			elif now == 0:
				counter += 1
			now = 1
			length = 0
	if now == -1:
		print(1)
	else:
		end = (length, now)
		chet_mass.sort()
		nechet_mass.sort()
		xxx = f(chet_mass, n // 2 - chet)
		yyy = f(nechet_mass, (n + 1) // 2 - nechet)
		minn = xxx[0] + yyy[0] + 2
		massiv = [xxx[1], yyy[1]]
		if end[0] <= massiv[end[1]]:
			massiv[end[1]] -= end[0]
			minn -= 1
		if begin[0] <= massiv[begin[1]]:
			minn -= 1
		minn += counter
		print(minn)


n = int(input())
s = map(int, input().split())
s = list(s)
import math
chet = 0
nechet = 0
posled = 1
perv = None
for i in range(len(s)):
	if s[i] == 0:
		continue
	elif s[i] % 2 == 0:
		chet = chet + 1
		posled = 2
		if perv is None:
			perv = 2
		s[i] = 2
	else:
		nechet = nechet + 1
		posled = 1
		if perv is None:
			perv = 1
		s[i] = 1
chet = len(s) // 2 - chet
nechet = math.ceil(len(s) / 2) - nechet
otvet = 0
for i in range(len(s) - 1):
	if s[i] != s[i + 1] and s[i] > 0 and (s[i + 1] > 0):
		otvet = otvet + 1
s = [3] + s + [3]
ss = []
l = None
for i in range(len(s)):
	if l is None:
		l = i
	elif s[i] != 0:
		if i - l > 1:
			ss.append((l + 1, i - 1, s[l], s[i]))
		l = i

def por(k):
	f = 2
	if k[2] == 3 or k[3] == 3:
		f = 1
	elif k[2] == k[3]:
		f = 0
	d = k[1] - k[0] + 1
	return (f, d)
ss.sort(key=por)
d = {1: nechet, 2: chet}
for k in ss:
	if k[2] == 3 and k[3] == 3:
		if k[1] - k[0] + 1 > 1:
			otvet = otvet + 1
	elif k[2] == k[3]:
		if d[k[2]] >= k[1] - k[0] + 1:
			d[k[2]] -= k[1] - k[0] + 1
		else:
			otvet = otvet + 2
	elif k[2] == 3:
		if d[k[3]] >= k[1] - k[0] + 1:
			d[k[3]] -= k[1] - k[0] + 1
		else:
			otvet = otvet + 1
	elif k[3] == 3:
		if d[k[2]] >= k[1] - k[0] + 1:
			d[k[2]] -= k[1] - k[0] + 1
		else:
			otvet = otvet + 1
	else:
		otvet = otvet + 1
print(otvet)


n = int(input())
arr = list(map(int, input().split()))
final = 0
if n % 2 == 0:
	(odd, even) = (n // 2, n // 2)
else:
	odd = n // 2 + 1
	even = n // 2
(temp, ind) = ([], [])
for i in range(n):
	if arr[i] == 0:
		arr[i] = None
	else:
		if arr[i] % 2 == 0:
			even -= 1
			arr[i] = arr[i] % 2
		else:
			odd -= 1
			arr[i] = arr[i] % 2
		temp.append(arr[i] % 2)
		ind.append(i)
for i in range(n - 1):
	if arr[i] != None and arr[i + 1] != None:
		l = [arr[i], arr[i + 1]]
		l.sort()
		if l == [0, 1]:
			final += 1
d = {'first': [], 'oddodd': [], 'eveneven': [], 'oddeven': [], 'last': []}
if ind == []:
	if n == 1:
		print(0)
		exit()
	else:
		print(1)
		exit()
if ind[0] != 0:
	d['first'].append(ind[0])
if ind[-1] != n - 1:
	d['last'].append(n - ind[-1] - 1)
for i in range(len(ind) - 1):
	if temp[i] == temp[i + 1]:
		if temp[i] == 1:
			d['oddodd'].append(ind[i + 1] - ind[i] - 1)
		else:
			d['eveneven'].append(ind[i + 1] - ind[i] - 1)
	else:
		d['oddeven'].append(ind[i + 1] - ind[i] - 1)
for i in d:
	p = []
	for j in d[i]:
		if j != 0:
			p.append(j)
	d[i] = p
values = d['oddodd']
values.sort()
ans = []
for i in range(len(values)):
	if values[i] != 0:
		if values[i] <= odd:
			odd -= values[i]
		else:
			ans.append(values[i])
d['oddodd'] = ans
values = d['eveneven']
values.sort()
ans = []
for i in range(len(values)):
	if values[i] != 0:
		if values[i] <= even:
			even -= values[i]
		else:
			ans.append(values[i])
d['eveneven'] = ans
if d['first'] != []:
	if temp[0] == 1:
		if odd >= d['first'][0]:
			odd -= d['first'][0]
			d['first'] = []
	elif even >= d['first'][0]:
		even -= d['first'][0]
		d['first'] = []
if d['last'] != []:
	if temp[-1] == 1:
		if odd >= d['last'][0]:
			odd -= d['last'][0]
			d['last'] = []
	elif even >= d['last'][0]:
		even -= d['last'][0]
		d['last'] = []
final += len(d['last'])
final += len(d['first'])
final += 2 * len(d['oddodd'])
final += 2 * len(d['eveneven'])
final += len(d['oddeven'])
print(final)


length = int(input())
inputlist = list(map(int, input().split()))
replicatelist = inputlist.copy()
sortedlist = list(range(1, length + 1))
complexity = 0
missingvalues = []
oddodd = 0
eveneven = 0
oddeven = 0
chaineveneven = []
chainoddodd = []
chainoddeven = []
odd = []
even = []
for i in range(len(inputlist) - 1):
	if inputlist[i] != 0:
		if inputlist[i] % 2 == inputlist[i + 1] % 2 and inputlist[i + 1] != 0:
			complexity += 0
		elif inputlist[i] % 2 != inputlist[i + 1] % 2 and inputlist[i + 1] != 0:
			complexity += 1
for i in range(length):
	value = inputlist[i]
	if value != 0:
		sortedlist[value - 1] = 'k'
for i in range(length):
	if sortedlist[i] != 'k':
		missingvalues.append(i + 1)
oddmissing = 0
evenmissing = 0
for b in missingvalues:
	if b % 2 == 0:
		evenmissing += 1
	else:
		oddmissing += 1

def chainedzeros(countervariable, inputlist):
	length = len(inputlist)
	chainedzeros = 0
	zerobefore = True
	while zerobefore and countervariable <= length - 1:
		if inputlist[countervariable] != 0:
			zerobefore = False
		else:
			chainedzeros += 1
			countervariable += 1
	if chainedzeros > 1:
		return [True, countervariable]
	else:
		return [False, countervariable]

def parity(leftvarcheck, rightvarcheck, chainedzeroscheck, leftvalue, rightvalue):
	global oddodd
	global eveneven
	global oddeven
	global odd
	global even
	global chaineveneven
	global chainoddodd
	global chaineeven
	global initialcounter
	global countervariable
	if (leftvarcheck == True and rightvarcheck == True) and chainedzeroscheck == True:
		if leftvalue % 2 == 0 and rightvalue % 2 == 0:
			chaineveneven.append(countervariable - initialcounter)
		elif leftvalue % 2 == 1 and rightvalue % 2 == 1:
			chainoddodd.append(countervariable - initialcounter)
		else:
			chainoddeven.append(countervariable - initialcounter)
	elif (leftvarcheck == False and rightvarcheck == True) and chainedzeroscheck == True:
		if rightvalue % 2 == 0:
			even.append(countervariable - initialcounter)
		else:
			odd.append(countervariable - initialcounter)
	elif (leftvarcheck == True and rightvarcheck == False) and chainedzeroscheck == True:
		if leftvalue % 2 == 0:
			even.append(countervariable - initialcounter)
		else:
			odd.append(countervariable - initialcounter)
	elif (leftvarcheck == True and rightvarcheck == True) and chainedzeroscheck == False:
		if leftvalue % 2 == 0 and rightvalue % 2 == 0:
			eveneven += 1
		elif leftvalue % 2 == 1 and rightvalue % 2 == 1:
			oddodd += 1
		else:
			oddeven += 1
	elif (leftvarcheck == True and rightvarcheck == False) and chainedzeroscheck == False:
		if leftvalue % 2 == 0:
			even.append(1)
		else:
			odd.append(1)
	elif (leftvarcheck == False and rightvarcheck == True) and chainedzeroscheck == False:
		if rightvalue % 2 == 0:
			even.append(1)
		else:
			odd.append(1)
countervariable = 0
leftvarcheck = False
leftvalue = None
rightvarcheck = True
while countervariable <= length - 1:
	alpha = inputlist[countervariable]
	if alpha == 0:
		initialcounter = countervariable
		if countervariable >= 1:
			leftvarcheck = True
			leftvalue = inputlist[countervariable - 1]
		chainedinfo = chainedzeros(countervariable, inputlist)
		if chainedinfo[0] == True:
			countervariable = chainedinfo[1]
			if countervariable <= length - 1:
				rightvalue = inputlist[countervariable]
				parity(leftvarcheck, rightvarcheck, chainedinfo[0], leftvalue, rightvalue)
			else:
				rightvarcheck = False
				rightvalue = None
				parity(leftvarcheck, rightvarcheck, chainedinfo[0], leftvalue, rightvalue)
		elif chainedinfo[0] == False:
			countervariable = chainedinfo[1]
			if countervariable <= length - 1:
				rightvalue = inputlist[countervariable]
				parity(leftvarcheck, rightvarcheck, chainedinfo[0], leftvalue, rightvalue)
			else:
				rightvarcheck = False
				rightvalue = None
				parity(leftvarcheck, rightvarcheck, chainedinfo[0], leftvalue, rightvalue)
	else:
		countervariable += 1

def insertion(inputlist):
	global oddodd
	global eveneven
	global oddeven
	global odd
	global even
	global chaineveneven
	global chainoddodd
	global chainoddeven
	global evenmissing
	global oddmissing
	global complexity
	if oddmissing + evenmissing == len(inputlist) and len(inputlist) > 1:
		return 1
	chaineveneven.sort()
	chaineveneven.reverse()
	chainoddodd.sort()
	chainoddodd.reverse()
	chainoddeven.sort()
	chainoddeven.reverse()
	even.sort()
	even.reverse()
	odd.sort()
	odd.reverse()
	while evenmissing != 0 and eveneven != 0:
		evenmissing += -1
		eveneven += -1
	while evenmissing != 0 and (len(chaineveneven) != 0 or len(even) != 0):
		if len(even) != 0 and len(chaineveneven) != 0 and (evenmissing < chaineveneven[-1]):
			evenmissing += -1
			even[-1] += -1
			if even[-1] == 0:
				even.pop()
		elif len(chaineveneven) != 0:
			evenmissing += -1
			chaineveneven[-1] += -1
			if chaineveneven[-1] == 0:
				chaineveneven.pop()
		elif len(even) != 0:
			evenmissing += -1
			even[-1] += -1
			if even[-1] == 0:
				even.pop()
	while oddmissing != 0 and oddodd != 0:
		oddmissing += -1
		oddodd += -1
	while oddmissing != 0 and (len(chainoddodd) != 0 or len(odd) != 0):
		if len(odd) != 0 and len(chainoddodd) != 0 and (oddmissing < chainoddodd[-1]):
			oddmissing += -1
			odd[-1] += -1
			if odd[-1] == 0:
				odd.pop()
		elif len(chainoddodd) != 0:
			oddmissing += -1
			chainoddodd[-1] += -1
			if chainoddodd[-1] == 0:
				chainoddodd.pop()
		elif len(odd) != 0:
			oddmissing += -1
			odd[-1] += -1
			if odd[-1] == 0:
				odd.pop()
	while oddmissing != 0 and len(chainoddeven) != 0:
		oddmissing += -1
		chainoddeven[-1] += -1
		if chainoddeven[-1] == 0:
			chainoddeven.pop()
			complexity += 1
	while evenmissing != 0 and len(chainoddeven) != 0:
		evenmissing += -1
		chainoddeven[-1] += -1
		if chainoddeven[-1] == 0:
			chainoddeven.pop()
			complexity += 1
	complexity += oddeven + len(chainoddeven) + 2 * len(chainoddodd) + 2 * len(chaineveneven) + 2 * oddodd + 2 * eveneven + len(even) + len(odd)
	return complexity
print(insertion(inputlist))


import sys
input = sys.stdin.readline
n = int(input())
b = list(map(int, input().split()))
dum = n // 2 + 1
nxtd_arr = [[[101, 101] for _ in range(dum)] for _ in range(n + 1)]
nxtd_arr[0][0][0] = nxtd_arr[0][0][1] = 0
for i in range(1, n + 1):
	if b[i - 1] == 0:
		for j in range(1, dum):
			nxtd_arr[i][j][0] = min(nxtd_arr[i - 1][j - 1][0], nxtd_arr[i - 1][j - 1][1] + 1)
		for j in range(dum):
			nxtd_arr[i][j][1] = min(nxtd_arr[i - 1][j][0] + 1, nxtd_arr[i - 1][j][1])
	elif b[i - 1] % 2 == 0:
		for j in range(1, dum):
			nxtd_arr[i][j][0] = min(nxtd_arr[i - 1][j - 1][0], nxtd_arr[i - 1][j - 1][1] + 1)
	else:
		for j in range(dum):
			nxtd_arr[i][j][1] = min(nxtd_arr[i - 1][j][0] + 1, nxtd_arr[i - 1][j][1])
print(min(nxtd_arr[-1][-1]))


n = int(input())
l = list(map(int, input().split()))
d = set([i for i in range(1, n + 1)])
for i in l:
	if i != 0:
		d.remove(i)
t = [0, 0]
for i in d:
	t[i % 2] += 1
l = [1] + l + [1]
z = -1
oe = []
e = []
o = []
edo = []
ede = []
for i in range(1, n + 1):
	if l[i] == 0:
		if z == -1:
			z = i - 1
			if i == n:
				if l[z] % 2 == 0:
					ede.append([z + 1, i])
				else:
					edo.append([z + 1, i])
				z = -1
			elif l[i + 1] != 0:
				if z == 0:
					if l[i + 1] % 2 == 0:
						ede.append([z + 1, i])
					else:
						edo.append([z + 1, i])
				elif l[z] % 2 == l[i + 1] % 2:
					if l[z] % 2 == 0:
						e.append([z + 1, i])
					else:
						o.append([z + 1, i])
				else:
					oe.append([z + 1, i])
				z = -1
		elif l[i + 1] == 0:
			continue
		else:
			if z == 0 or i == n:
				if z == 0:
					if i == n:
						ede.append([z + 1, i])
					elif l[i + 1] % 2 == 0:
						ede.append([z + 1, i])
					else:
						edo.append([z + 1, i])
				elif l[z] % 2 == 0:
					ede.append([z + 1, i])
				else:
					edo.append([z + 1, i])
			elif l[z] % 2 == l[i + 1] % 2:
				if l[i + 1] % 2 == 0:
					e.append([z + 1, i])
				else:
					o.append([z + 1, i])
			else:
				oe.append([z + 1, i])
			z = -1
o.sort(reverse=True, key=lambda a: a[1] - a[0])
e.sort(reverse=True, key=lambda a: a[1] - a[0])
oe.sort(reverse=True, key=lambda a: a[1] - a[0])
ede.sort(reverse=True, key=lambda a: a[1] - a[0])
edo.sort(reverse=True, key=lambda a: a[1] - a[0])
for i in range(len(o)):
	(x, y) = o.pop()
	if t[1] >= abs(y - x + 1):
		for j in range(x, y + 1):
			l[j] = 1
			t[1] -= 1
	else:
		o.append([x, y])
		break
for i in range(len(e)):
	(x, y) = e.pop()
	if t[0] >= abs(y - x + 1):
		for j in range(x, y + 1):
			l[j] = 2
			t[0] -= 1
	else:
		e.append([x, y])
		break
for i in range(len(ede)):
	(x, y) = ede.pop()
	if t[0] >= y - x + 1:
		for j in range(x, y + 1):
			l[j] = 2
			t[0] -= 1
	else:
		ede.append([x, y])
for i in range(len(edo)):
	(x, y) = edo.pop()
	if t[1] >= abs(y - x + 1):
		for j in range(x, y + 1):
			l[j] = 1
			t[1] -= 1
	else:
		edo.append([x, y])
		break
edge = ede + edo
for i in range(len(edge)):
	(x, y) = edge.pop()
	if x == 1 and y == n:
		f = x
		while t[0]:
			l[f] = 2
			t[0] -= 1
			f += 1
		while t[1]:
			l[f] = 1
			t[1] -= 1
			f += 1
	elif x == 1:
		if l[y + 1] % 2 == 0:
			while y >= x:
				if t[0]:
					l[y] = 2
					t[0] -= 1
					y -= 1
				else:
					l[y] = 1
					t[1] -= 1
					y -= 1
		else:
			while y >= x:
				if t[1]:
					l[y] = 1
					t[1] -= 1
					y -= 1
				else:
					l[y] = 2
					t[0] -= 1
					y -= 1
	elif l[x - 1] % 2 == 0:
		while y >= x:
			if t[0]:
				l[x] = 2
				t[0] -= 1
				x += 1
			else:
				l[x] = 1
				t[1] -= 1
				x += 1
	else:
		while y >= x:
			if t[1]:
				l[x] = 1
				t[1] -= 1
				x += 1
			else:
				l[x] = 2
				t[0] -= 1
				x += 1
o = o + e + oe
for i in range(len(o)):
	(x, y) = o.pop()
	if l[x - 1] % 2 == 0:
		while y >= x:
			if t[0]:
				l[x] = 2
				t[0] -= 1
				x += 1
			else:
				l[x] = 1
				t[1] -= 1
				x += 1
	else:
		while y >= x:
			if t[1]:
				l[x] = 1
				t[1] -= 1
				x += 1
			else:
				l[x] = 2
				t[0] -= 1
				x += 1
count = 0
for i in range(2, n + 1):
	if l[i] % 2 != l[i - 1] % 2:
		count += 1
print(count)


from functools import lru_cache
n = int(input())
arr = list(map(int, input().split()))
odds = evens = 0
for a in arr:
	if a != 0:
		odds += a % 2
		evens += a % 2 == 0

@lru_cache(None)
def parity(i, e, o, last=None):
	if i == n:
		return 0
	elif arr[i] == 0 and last == None:
		even = parity(i + 1, e - 1, o, 0) if e > 0 else float('inf')
		odd = parity(i + 1, e, o - 1, 1) if o > 0 else float('inf')
		return min(even, odd)
	elif last == None:
		return parity(i + 1, e, o, arr[i] % 2)
	elif arr[i] != 0:
		if arr[i] % 2 != last:
			return 1 + parity(i + 1, e, o, arr[i] % 2)
		else:
			return parity(i + 1, e, o, last)
	elif last == 1:
		if o != 0 and e != 0:
			return min(1 + parity(i + 1, e - 1, o, 0), parity(i + 1, e, o - 1, 1))
		elif o == 0:
			return 1 + parity(i + 1, e - 1, o, 0)
		else:
			return parity(i + 1, e, o - 1, 1)
	else:
		if o != 0 and e != 0:
			return min(1 + parity(i + 1, e, o - 1, 1), parity(i + 1, e - 1, o, 0))
		if e == 0:
			return 1 + parity(i + 1, e, o - 1, 1)
		else:
			return parity(i + 1, e - 1, o, 0)
print(parity(0, n // 2 - evens, (n + 1) // 2 - odds))


n = int(input())
x = list(map(int, input().split()))
(p1, p2, c) = ([0] * 101, [0] * 101, [0] * 2)
(c[1], c[0]) = (n // 2 + n % 2, n // 2)
(count, edge, ans, temp1, temp2) = (0, [[] for i in range(2)], 0, 0, 0)
for i in range(n):
	if x[i] == 0:
		count += 1
		if i == n - 1:
			edge[x[i - count] % 2].append(count)
			ans += 1
		if count == n:
			if n == 1:
				ans = 0
			break
	else:
		if count > 0 and i - count - 1 >= 0 and (x[i] % 2 == x[i - count - 1] % 2 == 1):
			p1[count] += 1
		elif count > 0 and i - count - 1 >= 0 and (x[i] % 2 == x[i - count - 1] % 2 == 0):
			p2[count] += 1
		elif count > 0 and i - count == 0:
			edge[x[i] % 2].append(count)
			ans += 1
		elif i > 0 and (count > 0 or x[i] % 2 != x[i - 1] % 2):
			ans += 1
		count = 0
		c[x[i] % 2] -= 1
for i in range(1, 100):
	temp1 = min(p1[i], c[1] // i)
	p1[i] -= temp1
	c[1] -= i * temp1
	temp2 = min(p2[i], c[0] // i)
	p2[i] -= temp2
	c[0] -= i * temp2
	ans += p1[i] * 2 + p2[i] * 2
for i in range(2):
	for i2 in range(len(edge[i])):
		if c[i] >= edge[i][i2]:
			ans -= 1
			c[i] -= edge[i][i2]
print(ans)


n = int(input())
x = y = 0
a = list(map(int, input().split()))
pref = [0]
for q in range(n):
	if a[q] != 0 and a[q] % 2 == 0:
		x += 1
	elif a[q] != 0:
		y += 1
	if a[q] % 2 == 0 and a[q] != 0:
		a[q] = 2
		pref.append(pref[-1])
	elif a[q] % 2 == 1:
		a[q] = 1
		pref.append(pref[-1])
	else:
		pref.append(pref[-1] + 1)
(k, m) = (n // 2 - x, (n + 1) // 2 - y)
d = [[[0, 0] for q in range(n + 1)]]
for q in range(n):
	d.append([])
	for q1 in range(pref[q + 1] + 1):
		if a[q] == 1 or (a[q] == 0 and q1 == 0):
			d[-1].append([float('inf'), min(d[-2][q1][0] + 1, d[-2][q1][1])])
		elif a[q] == 2:
			d[-1].append([min(d[-2][q1][0], d[-2][q1][1] + 1), float('inf')])
		else:
			if a[q] == 0 and pref[q + 1] - q1 == 0:
				d[-1].append([min(d[-2][q1 - 1][0], d[-2][q1 - 1][1] + 1), float('inf')])
			d[-1].append([min(d[-2][q1 - 1][0], d[-2][q1 - 1][1] + 1), min(d[-2][q1][0] + 1, d[-2][q1][1])])
	for q1 in range(pref[q + 1] + 1, n + 1):
		d[-1].append([0, 0])
print(min(d[-1][k][0], d[-1][k][1]))


import sys
from sys import stdin, stdout
import bisect
import math
import heapq

def modinv(n, p):
	return pow(n, p - 2, p)

def cin():
	return map(int, sin().split())

def ain():
	return list(map(int, sin().split()))

def sin():
	return input()

def inin():
	return int(input())
import math

def Divisors(n):
	l = []
	for i in range(1, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n // i == i:
				l.append(i)
			else:
				l.append(i)
				l.append(n // i)
	return l

def main():
	n = inin()
	a = ain()
	x = n // 2
	p = []
	q = []
	if n % 2 == 1:
		y = x + 1
	else:
		y = x
	i = 0
	j = +1
	f = -1
	ans = j = 0
	pp = []
	qq = []
	for i in range(n):
		if a[i] != 0:
			if a[i] % 2 == 1:
				y -= 1
			else:
				x -= 1
			if f == -1 or a[i] % 2 ^ f == 0:
				if a[i] % 2 == 1:
					if f == -1:
						pp.append(j)
					else:
						p.append(j)
					j = 0
					f = a[i]
				else:
					if f == -1:
						qq.append(j)
					else:
						q.append(j)
					j = 0
			else:
				ans += 1
				j = 0
			f = a[i] % 2
		else:
			j += 1
	if f % 2 == 0:
		qq.append(j)
	else:
		pp.append(j)
	p.sort()
	q.sort()
	an = ans
	xx = x
	yy = y
	pp.sort()
	qq.sort()
	for i in pp:
		y -= i
		if i == 0:
			continue
		if y < 0:
			ans += 1
	for i in qq:
		x -= i
		if i == 0:
			continue
		if x < 0:
			ans += 1
	for i in p:
		y -= i
		if i == 0:
			continue
		if y < 0:
			ans += 2
	for i in q:
		x -= i
		if i == 0:
			continue
		if x < 0:
			ans += 2
	x = xx
	y = yy
	for i in p:
		y -= i
		if y < 0:
			y += i
			an += 2
	for i in q:
		x -= i
		if x < 0:
			x += i
			an += 2
	for i in pp:
		y -= i
		if y < 0:
			y += i
			an += 1
	for i in qq:
		x -= i
		if x < 0:
			x += i
			an += 1
	if ans == 0 and n > 1:
		ans = 1
	print(min(an, ans))
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'

def readnumbers(zero=0):
	conv = ord if py2 else lambda x: x
	A = []
	numb = zero
	sign = 1
	i = 0
	s = sys.stdin.buffer.read()
	try:
		while True:
			if s[i] >= b'0'[0]:
				numb = 10 * numb + conv(s[i]) - 48
			elif s[i] == b'-'[0]:
				sign = -1
			elif s[i] != b'\r'[0]:
				A.append(sign * numb)
				numb = zero
				sign = 1
			i += 1
	except:
		pass
	if s and s[-1] >= b'0'[0]:
		A.append(sign * numb)
	return A
main()


n = int(input())
p = [0] + list(map(int, input().split()))
dp = [[[10 ** 18] * 2 for i in range(n // 2 + 1)] for j in range(n + 1)]
dp[0][0][0] = dp[0][0][1] = 0
for i in range(1, n + 1):
	if p[i] == 0:
		for j in range(1, n // 2 + 1):
			dp[i][j][0] = min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1] + 1)
		for j in range(n // 2 + 1):
			dp[i][j][1] = min(dp[i - 1][j][0] + 1, dp[i - 1][j][1])
	elif p[i] % 2 == 0:
		for j in range(1, n // 2 + 1):
			dp[i][j][0] = min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1] + 1)
	else:
		for j in range(n // 2 + 1):
			dp[i][j][1] = min(dp[i - 1][j][0] + 1, dp[i - 1][j][1])
print(min(dp[-1][-1]))


n = int(input())
pr = 0
t = 0
ch = n // 2
nech = n // 2 + n % 2
mass1 = []
mass3 = []
answer = 0
for i in [int(x) for x in input().split()]:
	if i == 0:
		pr += 1
	elif pr > 0:
		if i % 2 == 0:
			ch -= 1
		else:
			nech -= 1
		if t == 0:
			t = i % 2 + 1
			mass1.append([pr, t])
		else:
			if t == i % 2 + 1:
				mass3.append([pr, t])
			else:
				answer += 1
			t = i % 2 + 1
		pr = 0
	else:
		if i % 2 == 0:
			ch -= 1
		else:
			nech -= 1
		if t != i % 2 + 1 and t != 0:
			answer += 1
		t = i % 2 + 1
if pr != 0:
	mass1.append([pr, t])
mass3.sort()
mass1.sort()
for l in mass3:
	if l[1] == 1:
		if ch >= l[0]:
			ch -= l[0]
		else:
			nech -= l[0] - ch
			answer += 2
	elif nech >= l[0]:
		nech -= l[0]
	else:
		ch -= l[0] - nech
		answer += 2
for l in mass1:
	if l[1] == 1:
		if ch >= l[0]:
			ch -= l[0]
		else:
			nech -= l[0] - ch
			ch = 0
			answer += 1
	elif nech >= l[0]:
		nech -= l[0]
	else:
		ch -= l[0] - nech
		nech = 0
		answer += 1
print(answer)


N = int(input())
A = [int(a) for a in input().split()]
M = A.count(0)
A2 = [a % 2 for a in A]
O = A2.count(1)
E = N - M - O
O = (N + 1) // 2 - O
E = N // 2 - E
C = [M]
for a in A:
	C.append(C[-1] - (a == 0))
X = [[999] * 102 for _ in range(N)]
Y = [[999] * 102 for _ in range(N)]
if A[0] % 2:
	X[0][O] = 0
elif A[0]:
	Y[0][O] = 0
else:
	if O:
		X[0][O - 1] = 0
	if E:
		Y[0][O] = 0
for i in range(1, N):
	for j in range(N + 1):
		if A[i] % 2:
			X[i][j] = min(X[i - 1][j], Y[i - 1][j] + 1)
		elif A[i]:
			Y[i][j] = min(X[i - 1][j] + 1, Y[i - 1][j])
		else:
			X[i][j] = min(X[i - 1][j + 1], Y[i - 1][j + 1] + 1)
			Y[i][j] = min(X[i - 1][j] + 1, Y[i - 1][j])
print(min(X[N - 1][0], Y[N - 1][0]))


n = int(input())
p = list(map(int, input().split()))
if n == 1:
	print(0)
	exit(0)
if sum(p) == 0:
	print(1)
	exit(0)
INF = 100
dp = [[INF] * 2 for _ in range(n // 2 + 1)]
if p[0] == 0:
	dp[1][0] = 0
	dp[0][1] = 0
elif p[0] % 2:
	dp[0][1] = 0
else:
	dp[1][0] = 0
for i in range(1, n):
	newdp = [[INF] * 2 for _ in range(n // 2 + 1)]
	if p[i] == 0:
		for j in range(n // 2 + 1):
			newdp[j][1] = min(dp[j][1], dp[j][0] + 1)
			if j == n // 2:
				break
			newdp[j + 1][0] = min(dp[j][0], dp[j][1] + 1)
	elif p[i] % 2:
		for j in range(n // 2 + 1):
			newdp[j][1] = min(dp[j][1], dp[j][0] + 1)
	else:
		for j in range(n // 2):
			newdp[j + 1][0] = min(dp[j][0], dp[j][1] + 1)
	dp = newdp
print(min(dp[-1]))


from math import *
n = int(input())
a = [int(x) for x in input().split()]
odd = int(ceil(n / 2))
even = n - odd
dp = [[[10 ** 8 for i in range(2)] for j in range(even + 2)] for k in range(n)]
if n <= 2:
	print(n - 1)
	exit(0)
for i in range(0, n):
	if i == 0:
		if a[i] == 0:
			dp[i][even][0] = 0
			dp[i][even][1] = 0
			dp[i][even - 1][0] = 0
		elif a[i] % 2 == 0:
			dp[i][even - 1][0] = 0
		else:
			dp[i][even][1] = 0
	elif a[i] == 0:
		for j in range(even, -1, -1):
			dp[i][j][0] = min(dp[i - 1][j + 1][1] + 1, dp[i - 1][j + 1][0])
			dp[i][j][1] = min(dp[i - 1][j][0] + 1, dp[i - 1][j][1])
	elif a[i] % 2 == 0:
		for j in range(even, -1, -1):
			dp[i][j][0] = min(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1] + 1)
	elif a[i] % 2 == 1:
		for j in range(even, -1, -1):
			dp[i][j][1] = min(dp[i - 1][j][0] + 1, dp[i - 1][j][1])
print(min(dp[n - 1][0][0], dp[n - 1][0][1]))


n = int(input())
arr = list(map(lambda x: int(x), input().split(' ')))
count_ans = 0
arr_1 = []
for i in range(n - 1):
	if (arr[i] + arr[i + 1]) % 2 == 1 and arr[i] != 0 and (arr[i + 1] != 0):
		count_ans += 1
prev = -1
count = 0
count_odd = 0
count_even = 0
for i in range(n):
	if arr[i] % 2 == 1:
		count_odd += 1
	if arr[i] % 2 == 0 and arr[i] != 0:
		count_even += 1
	if arr[i] == 0:
		count += 1
	elif arr[i] != 0:
		if count != 0:
			arr_1.append([count, prev, arr[i]])
		prev = arr[i]
		count = 0
flag = False
if count_odd == 0 and count_even == 0:
	flag = True
if count != 0:
	arr_1.append([count, prev, -1])
t_c_odd = n - n // 2
t_c_even = n // 2
a_count_odd = t_c_odd - count_odd
a_count_even = t_c_even - count_even
arr_odd = []
arr_even = []
arr_later = []
for i in arr_1:
	if (i[1] + i[2]) % 2 == 0 and i[1] != -1 and (i[2] != -1) and (i[1] % 2 == 1):
		arr_odd.append(i)
	elif (i[1] + i[2]) % 2 == 0 and i[1] != -1 and (i[2] != -1) and (i[1] % 2 == 0):
		arr_even.append(i)
	if (i[1] + i[2]) % 2 == 1 and i[1] != -1 and (i[2] != -1):
		count_ans += 1
	if i[1] == -1 or i[2] == -1:
		arr_later.append(i)
arr_odd.sort()
arr_even.sort()
pre_odd = []
pre_even = []
for i in arr_odd:
	if len(pre_odd) == 0:
		pre_odd.append(i[0])
	else:
		pre_odd.append(pre_odd[-1] + i[0])
for i in arr_even:
	if len(pre_even) == 0:
		pre_even.append(i[0])
	else:
		pre_even.append(pre_even[-1] + i[0])
if len(pre_even) > 0:
	if pre_even[-1] <= a_count_even:
		a_count_even = a_count_even - pre_even[-1]
	elif pre_even[0] > a_count_even:
		a_count_even = a_count_even
		count_ans += 2 * len(pre_even)
	else:
		for i in range(len(pre_even) - 1):
			if pre_even[i] <= a_count_even and a_count_even < pre_even[i + 1]:
				count_ans += 2 * (len(pre_even) - i - 1)
				a_count_even = a_count_even - pre_even[i]
if len(pre_odd) > 0:
	if pre_odd[-1] <= a_count_odd:
		a_count_odd = a_count_odd - pre_odd[-1]
	elif pre_odd[0] > a_count_odd:
		a_count_odd = a_count_odd
		count_ans += 2 * len(pre_odd)
	else:
		for i in range(len(pre_odd) - 1):
			if pre_odd[i] <= a_count_odd and a_count_odd < pre_odd[i + 1]:
				count_ans += 2 * (len(pre_odd) - i - 1)
				a_count_odd = a_count_odd - pre_odd[i]
for i in arr_later:
	if i[1] == -1:
		if i[2] % 2 == 0 and a_count_even < i[0]:
			count_ans += 1
		elif i[2] % 2 == 1 and a_count_odd < i[0]:
			count_ans += 1
	if i[2] == -1:
		if i[1] % 2 == 0 and a_count_even < i[0]:
			count_ans += 1
		elif i[1] % 2 == 1 and a_count_odd < i[0]:
			count_ans += 1
if flag == True and n >= 2:
	print(1)
else:
	print(count_ans)


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7
N = INT()
A = LIST()
A = [a % 2 if a != 0 else -1 for a in A]
M = ceil(N, 2)
dp = list3d(N + 1, M + 1, 2, INF)
dp[0][0][0] = dp[0][0][1] = 0
for i in range(N):
	a = A[i]
	for j in range(M + 1):
		for k in range(2):
			if (a == 1 or a == -1) and j + 1 <= M:
				dp[i + 1][j + 1][1] = min(dp[i + 1][j + 1][1], dp[i][j][k] + (1 ^ k))
			if a == 0 or a == -1:
				dp[i + 1][j][0] = min(dp[i + 1][j][0], dp[i][j][k] + (0 ^ k))
ans = min(dp[N][M][0], dp[N][M][1])
print(ans)


def main():
	n = int(input())
	a = readIntArr()
	arr = []
	items = set(range(1, n + 1))
	for x in a:
		if x == 0:
			arr.append(-1)
		else:
			arr.append(x % 2)
			items.remove(x)
	itemModCnts = [0, 0]
	for x in items:
		itemModCnts[x % 2] += 1
	dp = makeArr(inf, [n, n + 1, 2])
	cumuUnknown = 0
	if arr[0] == -1:
		dp[0][0][1] = 0
		dp[0][1][0] = 0
		cumuUnknown += 1
	else:
		dp[0][0][arr[0] % 2] = 0
	for i in range(1, n):
		if arr[i] == -1:
			cumuUnknown += 1
			for j in range(cumuUnknown + 1):
				if j > 0:
					dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j - 1][0])
					dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j - 1][1] + 1)
				usedOddCnts = cumuUnknown - j
				if usedOddCnts > 0:
					dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][0] + 1)
					dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][1])
		else:
			for j in range(n):
				dp[i][j][arr[i]] = min(dp[i][j][arr[i]], dp[i - 1][j][arr[i]])
				dp[i][j][arr[i]] = min(dp[i][j][arr[i]], 1 + dp[i - 1][j][arr[i] ^ 1])
	ans = min(dp[n - 1][itemModCnts[0]][0], dp[n - 1][itemModCnts[0]][1])
	print(ans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultVal, dimensionArr):
	dv = defaultVal
	da = dimensionArr
	if len(da) == 1:
		return [dv for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x, y):
	print('? {} {}'.format(x, y))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


n = int(input())
s = list(map(int, input().split()))
dp = [[[float('INF'), float('INF')] for i in range(n // 2 + 1)] for i in range(n + 1)]
dp[0][0] = [0, 0]
for i in range(1, n + 1):
	if s[i - 1] == 0:
		for j in range(1, n // 2 + 1):
			dp[i][j][0] = min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1] + 1)
		for j in range(n // 2 + 1):
			dp[i][j][1] = min(dp[i - 1][j][0] + 1, dp[i - 1][j][1])
	elif s[i - 1] % 2 == 0:
		for j in range(1, n // 2 + 1):
			dp[i][j][0] = min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1] + 1)
	else:
		for j in range(n // 2 + 1):
			dp[i][j][1] = min(dp[i - 1][j][0] + 1, dp[i - 1][j][1])
print(min(dp[-1][-1]))


from math import *
n = int(input())
a = list(map(int, input().split()))
o = e = 0
if n == 1:
	print(0)
	exit(0)
for i in a:
	if i == 0:
		continue
	if i & 1:
		o += 1
	else:
		e += 1
o = ceil(n / 2) - o
e = n // 2 - e
l1 = l2 = 0
il1 = il2 = 0
ans = 0
ct = []
ect = []
for i in range(1, n):
	if a[i] != 0 and a[i - 1] != 0:
		if a[i] % 2 != a[i - 1] % 2:
			ans += 1
i = 0
while i < n:
	st = i - 1
	while i < n and a[i] == 0:
		i += 1
	end = i
	l = end - st - 1
	if l > 0:
		if st == -1:
			l1 = l
			il1 = end
		elif end == n:
			l2 = l
			il2 = st
		elif a[st] % 2 != a[end] % 2:
			ans += 1
		elif a[st] % 2 == 0:
			ect.append(l)
		else:
			ct.append(l)
	i += 1
ct.sort()
for i in ct:
	if i <= o:
		o -= i
	else:
		ans += 2
ect.sort()
for i in ect:
	if i <= e:
		e -= i
	else:
		ans += 2
if l1:
	if l1 == n:
		print(1)
		exit(0)
	if a[il1] % 2 == 0:
		if e >= l1:
			e -= l1
		else:
			ans += 1
	elif o >= l1:
		o -= l1
	else:
		ans += 1
if l2:
	if a[il2] % 2 == 0:
		if e >= l2:
			e -= l2
		else:
			ans += 1
	elif o >= l2:
		o -= l2
	else:
		ans += 1
print(ans)


import math
n = int(input())
y = n // 2
x = n - y
a = [0]
s = input().split(' ')
for i in range(1, n + 1):
	a.append(int(s[i - 1]))
if n == 1:
	print(0)
	exit()
inf = 99999999
dp = [[], []]
for i in range(y + 1):
	dp[1].append([inf, inf])
if a[1] > 0:
	if a[1] % 2 == 0:
		dp[1][1][0] = 0
	else:
		dp[1][0][1] = 0
else:
	dp[1][1][0] = 0
	dp[1][0][1] = 0
for i in range(2, n + 1):
	dp.append([])
	for j in range(y + 1):
		dp[i].append([inf, inf])
		if a[i] > 0:
			if a[i] % 2 == 0:
				if j > 0:
					dp[i][j][0] = min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1] + 1)
			else:
				dp[i][j][1] = min(dp[i - 1][j][1], dp[i - 1][j][0] + 1)
		else:
			if j > 0:
				dp[i][j][0] = min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1] + 1)
			dp[i][j][1] = min(dp[i - 1][j][1], dp[i - 1][j][0] + 1)
print(min(dp[n][y][0], dp[n][y][1]))


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)
	exit()
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
	elif 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]))


n = int(input())
p = [int(x) for x in input().split()]
pi = [i for i in range(len(p)) if p[i] != 0]
(even, odd) = (0, 0)
ans = 0
(ee, oo) = ([], [])
oe = 0
for x in p:
	if x != 0:
		if x & 1:
			odd += 1
		else:
			even += 1
st = [-1, -1]
en = [-1, -1]
if len(pi) > 0 and pi[0] > 0:
	st = [p[pi[0]] & 1, pi[0]]
if len(pi) > 0 and pi[-1] < n - 1:
	en = [p[pi[-1]] & 1, n - 1 - pi[-1]]
for i in range(1, len(pi)):
	t = pi[i] - pi[i - 1] - 1
	if p[pi[i]] & 1 == p[pi[i - 1]] & 1:
		if p[pi[i]] & 1:
			oo.append(t)
		else:
			ee.append(t)
	else:
		oe += 1
odd = (n + (n & 1)) // 2 - odd
even = (n - (n & 1)) // 2 - even
oo.sort()
ee.sort()
(s, se, so) = (0, len(ee), len(oo))
(le, lo) = (even, odd)
for i in range(len(ee)):
	s += ee[i]
	le = even - s
	if le < 0:
		le += ee[i]
		se = i
		break
s = 0
for i in range(len(oo)):
	s += oo[i]
	lo = odd - s
	if lo < 0:
		lo += oo[i]
		so = i
		break
ans += 2 * (len(ee) - se) + 2 * (len(oo) - so) + oe
if st[0] != -1 and en[0] != -1:
	if st[1] > en[1]:
		(st, en) = (en, st)
if st[0] != -1:
	if st[0]:
		if lo < st[1]:
			ans += 1
		else:
			lo -= st[1]
	elif le < st[1]:
		ans += 1
	else:
		le -= st[1]
if en[0] != -1:
	if en[0]:
		if lo < en[1]:
			ans += 1
		else:
			lo = 0
	elif le < en[1]:
		ans += 1
	else:
		le = 0
if len(pi) == 0 and len(p) > 1:
	ans = 1
print(ans)


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]))


from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def fun(pos, odd, even, last):
	if pos == n:
		if odd == 0 and even == 0:
			return 0
		else:
			return 1000000007
	if dp[pos][odd][even][last] != -1:
		return dp[pos][odd][even][last]
	if a[pos]:
		k = 0
		if a[pos] & 1:
			k = 1
		k1 = k ^ last
		if k1:
			return 1 + fun(pos + 1, odd, even, k)
		else:
			return fun(pos + 1, odd, even, k)
	ans = 1000000007
	if last & 1:
		if odd > 0:
			ans = min(ans, fun(pos + 1, odd - 1, even, 1))
		if even > 0:
			ans = min(ans, 1 + fun(pos + 1, odd, even - 1, 0))
	else:
		if odd > 0:
			ans = min(ans, 1 + fun(pos + 1, odd - 1, even, 1))
		if even > 0:
			ans = min(ans, fun(pos + 1, odd, even - 1, 0))
	dp[pos][odd][even][last] = ans
	return ans

def solve():
	global n
	n = ii()
	global a
	a = li()
	o = n // 2
	e = n // 2
	if n & 1:
		o += 1
	for i in a:
		if i == 0:
			continue
		if i & 1:
			o -= 1
		else:
			e -= 1
	global dp
	dp = [[[[-1 for i in range(2)] for j in range(105)] for k in range(105)] for k1 in range(n)]
	ans = min(fun(0, o, e, 0), fun(0, o, e, 1))
	print(ans)
solve()


n = int(input())
p = list(map(int, input().split()))
total_chet = n // 2
total_nechet = n // 2 + n % 2
hang_chet = len([item for item in p if item > 0 and item % 2 == 0])
hang_nechet = len([item for item in p if item > 0 and item % 2 == 1])
rest_chet = total_chet - hang_chet
rest_nechet = total_nechet - hang_nechet
pred = 'None'
chet_needed_lens = []
nechet_needed_lens = []
edge_start = []
edge_finish = []
given_compl = 0
mixed_count = 0
cur_zero_count = 0
for item in p:
	if item == 0:
		cur_zero_count += 1
	else:
		if item % 2 == 0:
			if pred == 'chet':
				chet_needed_lens.append(cur_zero_count)
			elif pred == 'nechet':
				if cur_zero_count > 0:
					mixed_count += 1
				else:
					given_compl += 1
			elif pred == 'None':
				edge_start = ['chet', cur_zero_count]
			else:
				print('Invalid State, line 40')
			pred = 'chet'
		else:
			if pred == 'nechet':
				nechet_needed_lens.append(cur_zero_count)
			elif pred == 'chet':
				if cur_zero_count > 0:
					mixed_count += 1
				else:
					given_compl += 1
			elif pred == 'None':
				edge_start = ['nechet', cur_zero_count]
			else:
				print('Invalid state, line 50, pred = {}'.format(pred))
			pred = 'nechet'
		cur_zero_count = 0
	edge_finish = [pred, cur_zero_count]
chet_needed_lens.sort()
nechet_needed_lens.sort()
i = 0
while i < len(chet_needed_lens) and chet_needed_lens[i] <= rest_chet:
	rest_chet -= chet_needed_lens[i]
	i += 1
chet_compl = 2 * (len(chet_needed_lens) - i)
i = 0
while i < len(nechet_needed_lens) and nechet_needed_lens[i] <= rest_nechet:
	rest_nechet -= nechet_needed_lens[i]
	i += 1
nechet_compl = 2 * (len(nechet_needed_lens) - i)
start_compl = 0
if len(edge_start) > 0:
	if edge_start[0] == 'nechet':
		if rest_nechet >= edge_start[1]:
			rest_nechet -= edge_start[1]
			start_compl += 0
		else:
			start_compl += 1
	elif rest_chet >= edge_start[1]:
		rest_chet -= edge_start[1]
		start_compl += 0
	else:
		start_compl += 1
finish_compl = 0
if edge_finish[0] == 'nechet':
	if rest_nechet >= edge_finish[1]:
		finish_compl += 0
	else:
		finish_compl += 1
elif edge_finish[0] == 'chet':
	if rest_chet >= edge_finish[1]:
		rest_chet -= edge_finish[1]
		finish_compl += 0
	else:
		finish_compl += 1
elif edge_finish[0] == 'None':
	if n > 1:
		finish_compl += 1
else:
	print('Invalid State')
ans = given_compl + mixed_count + chet_compl + nechet_compl + start_compl + finish_compl
print(ans)


import math
n = int(input())
even = n // 2
odd = (n + 1) // 2
p = list(map(int, input().split()))
used_up = [0]
for x in p:
	if x != 0:
		even -= (x + 1) % 2
		odd -= x % 2
		used_up.append(used_up[-1])
	else:
		used_up.append(used_up[-1] + 1)
total = even + odd
dp_array = [[[None, None] for i in range(even + 1)] for j in range(n)]

def min_complexity(i, even_left, previous_even):
	if i == n:
		return 0
	if dp_array[i][even_left][previous_even] == None:
		if p[i] != 0:
			dp_array[i][even_left][previous_even] = min_complexity(i + 1, even_left, int(p[i] % 2 == 0)) + 1 - (p[i] % 2 == 1 - previous_even)
		else:
			odd_left = total - used_up[i] - even_left
			val = math.inf
			if even_left > 0:
				val = min_complexity(i + 1, even_left - 1, 1) + (1 - previous_even)
			if odd_left > 0:
				val = min(val, min_complexity(i + 1, even_left, 0) + previous_even)
			dp_array[i][even_left][previous_even] = val
	return dp_array[i][even_left][previous_even]
x = min(min_complexity(0, even, 0), min_complexity(0, even, 1))
print(x)


def main():
	n = int(input())
	a = input()
	even_count = int(n / 2)
	odd_count = n - even_count
	result = 0
	arr = list(map(int, a.split()))
	left = -1
	right = -1
	odd = {}
	even = {}
	diff = 0
	zero = 0
	special_odd = {}
	special_even = {}
	for x in arr:
		if x == 0:
			zero += 1
			continue
		if x % 2 == 1:
			odd_count -= 1
		else:
			even_count -= 1
		if left == -1:
			if zero != 0:
				if x % 2 == 1:
					special_odd[zero] = special_odd[zero] + 1 if zero in special_odd else 1
				else:
					special_even[zero] = special_even[zero] + 1 if zero in special_even else 1
			left = x
			zero = 0
			continue
		if x != 0 and zero == 0:
			if left % 2 != x % 2:
				result += 1
			left = x
			continue
		right = x
		if left % 2 == right % 2:
			if left % 2 == 1:
				odd[zero] = odd[zero] + 1 if zero in odd else 1
			else:
				even[zero] = even[zero] + 1 if zero in even else 1
		else:
			diff += 1
		zero = 0
		left = x
		right = -1
	if right == -1 and zero != 0:
		if left % 2 == 1:
			special_odd[zero] = special_odd[zero] + 1 if zero in special_odd else 1
		else:
			special_even[zero] = special_even[zero] + 1 if zero in special_even else 1
	for (key, value) in sorted(odd.items()):
		counter = value
		while counter > 0 and odd_count >= key:
			odd_count -= key
			counter -= 1
		if counter == 0:
			continue
		if odd_count < key:
			result += 2 * counter
	for (key, value) in sorted(even.items()):
		counter = value
		while counter > 0 and even_count >= key:
			even_count -= key
			counter -= 1
		if counter == 0:
			continue
		if even_count < key:
			result += 2 * counter
	for (key, value) in sorted(special_odd.items()):
		counter = value
		while counter > 0 and odd_count >= key:
			odd_count -= key
			counter -= 1
		if counter == 0:
			continue
		if odd_count < key:
			result += 1 * counter
	for (key, value) in sorted(special_even.items()):
		counter = value
		while counter > 0 and even_count >= key:
			even_count -= key
			counter -= 1
		if counter == 0:
			continue
		if even_count < key:
			result += 1 * counter
	result += diff
	print(result)
main()


prime = 1000000007
t = 1
for test in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		b = set(a)
		if len(b) == 1:
			print(1)
		else:
			even = 0
			odd = 0
			for i in range(1, n + 1):
				if i not in b:
					if i % 2 == 0:
						even += 1
					else:
						odd += 1
			ans = 0
			prev = a[0]
			for i in a:
				if i != 0 and prev != 0 and (i % 2 != prev % 2):
					ans += 1
				prev = i
			solve_first = []
			ind = 0
			while a[ind] == 0:
				ind += 1
			prev = a[ind]
			count = ind
			if ind != 0:
				tmp = 0
				left_count = count
				left_parity = prev % 2
			else:
				tmp = 1
				left_count = 0
				left_parity = prev % 2
			while ind < n:
				if a[ind] != 0:
					if count != 0:
						if prev % 2 == a[ind] % 2:
							solve_first.append((count, tmp, prev % 2))
							if tmp == 0:
								tmp = 1
						else:
							ans += 1
					prev = a[ind]
					count = 0
				else:
					count += 1
				ind += 1
			if count != 0:
				right_count = count
				right_parity = prev % 2
				solve_first.append((count, 2, prev % 2))
			else:
				right_count = 0
				right_parity = prev % 2
			solve_first.sort()
			found_left = False
			found_right = False
			for (count, non_corner, parity) in solve_first:
				if non_corner == 0:
					found_left = True
				if non_corner == 2:
					found_right = True
				if parity == 0:
					if even < count:
						if non_corner == 1:
							ans += 2
							if count - even <= left_count and found_left and (left_parity == parity):
								ans -= 1
							elif count - even <= right_count and found_right and (right_parity == parity):
								ans -= 1
						else:
							ans += 1
						odd -= count - even
						even = 0
					else:
						even -= count
				elif odd < count:
					if non_corner == 1:
						ans += 2
						if count - odd <= left_count and found_left and (left_parity == parity):
							ans -= 1
						elif count - odd <= right_count and found_right and (right_parity == parity):
							ans -= 1
					else:
						ans += 1
					even -= count - odd
					odd = 0
				else:
					odd -= count
			print(ans)


n = int(input())
a = list(map(int, input().split()))
s = set(a)
(u, v) = (0, 0)
for i in range(1, n + 1):
	if i not in s:
		if i & 1:
			u += 1
		else:
			v += 1
dp = [[[[n] * (v + 1) for _ in range(u + 1)] for _ in range(2)] for _ in range(n + 1)]
dp[0][0][u][v] = 0
for i in range(1, n + 1):
	ai = a[i - 1]
	if ai == 0:
		for pp in range(2):
			for qp in range(2):
				w = int(pp != qp) if i > 1 else 0
				for p in range(u + 1):
					for q in range(v + 1):
						if qp == 1 and p + 1 <= u:
							dp[i][qp][p][q] = min(dp[i][qp][p][q], dp[i - 1][pp][p + 1][q] + w)
						elif qp == 0 and q + 1 <= v:
							dp[i][qp][p][q] = min(dp[i][qp][p][q], dp[i - 1][pp][p][q + 1] + w)
	elif ai & 1:
		w = int(i > 1)
		for p in range(u + 1):
			for q in range(v + 1):
				dp[i][1][p][q] = min(dp[i - 1][0][p][q] + w, dp[i - 1][1][p][q])
	else:
		w = int(i > 1)
		for p in range(u + 1):
			for q in range(v + 1):
				dp[i][0][p][q] = min(dp[i - 1][1][p][q] + w, dp[i - 1][0][p][q])
print(min(dp[n][0][0][0], dp[n][1][0][0]))


n = int(input().strip())
(even, odd) = (n // 2, n // 2 + n % 2)
ints = list(map(int, input().split()))
(prev, previ, count) = (None, -1, 0)
complexity = 0
groups = []
for (i, x) in enumerate(ints):
	if x == 0:
		count += 1
	else:
		if not prev:
			if count:
				groups.append((1, -count, x % 2))
		elif prev % 2 == x % 2:
			if count:
				groups.append((2, -count, x % 2))
		else:
			complexity += 1
		if x % 2:
			odd -= 1
		else:
			even -= 1
		count = 0
		prev = x
else:
	if count:
		if prev:
			groups.append((1, -count, prev % 2))
		elif n % 2 == 0:
			complexity = 1
if groups:
	groups.sort(reverse=True)
	for g in groups:
		if g[2]:
			if odd + g[1] < 0:
				complexity += g[0]
			else:
				odd += g[1]
		elif even + g[1] < 0:
			complexity += g[0]
		else:
			even += g[1]
print(complexity)


import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
EVEN = n // 2
ODD = n - n // 2
DP = dict()
DP[0, 0, 0] = 0
DP[1, 0, 0] = 0
from collections import defaultdict
for i in range(n):
	a = A[i]
	SUM = i + 1
	NDP = defaultdict(int)
	if a != 0:
		if a % 2 == 0:
			for j in range(SUM + 1):
				NDP[0, j, SUM - j] = min(DP.get((0, j - 1, SUM - j), 1 << 32), DP.get((1, j - 1, SUM - j), 1 << 32) + 1)
		else:
			for j in range(SUM + 1):
				NDP[1, j, SUM - j] = min(DP.get((0, j, SUM - j - 1), 1 << 32) + 1, DP.get((1, j, SUM - j - 1), 1 << 32))
	else:
		for j in range(SUM + 1):
			NDP[0, j, SUM - j] = min(DP.get((0, j - 1, SUM - j), 1 << 32), DP.get((1, j - 1, SUM - j), 1 << 32) + 1)
			NDP[1, j, SUM - j] = min(DP.get((0, j, SUM - j - 1), 1 << 32) + 1, DP.get((1, j, SUM - j - 1), 1 << 32))
	DP = NDP
ANS = 1 << 32
print(min(DP.get((0, EVEN, ODD), 1 << 32), DP.get((1, EVEN, ODD), 1 << 32)))


from math import ceil, floor
n = int(input())
a = input().split(' ')
arr = []
(o, e, arr) = (ceil(n / 2), floor(n / 2), [])
for i in a:
	num = int(i)
	if num % 2 != 0:
		o = o - 1
	elif num > 0:
		e = e - 1
	arr.append(num)
(oa, ea, of, ef, cnt, f) = ([], [], False, False, 0, True)
ans = 0
(e1, o1) = ([], [])
for i in arr:
	if i == 0:
		cnt = cnt + 1
	else:
		if f:
			if i % 2 == 0:
				e1.append(cnt)
				ef = True
			else:
				o1.append(cnt)
				of = True
			cnt = 0
		elif of:
			if i % 2 == 0:
				ef = True
				ans = ans + 1
				of = False
			else:
				oa.append(cnt)
			cnt = 0
		elif ef:
			if i % 2 == 0:
				ea.append(cnt)
			else:
				of = True
				ef = False
				ans = ans + 1
			cnt = 0
		elif i % 2 == 0:
			ef = True
		else:
			of = True
		f = False
if cnt == n:
	print(min(1, n - 1))
else:
	if of:
		o1.append(cnt)
	elif ef:
		e1.append(cnt)
	oa.sort()
	ea.sort()
	o1.sort()
	e1.sort()
	(op, ep) = (len(oa), len(ea))
	for i in oa:
		if o >= i:
			op = op - 1
			o = o - i
		else:
			break
	for i in ea:
		if e >= i:
			ep = ep - 1
			e = e - i
		else:
			break
	for i in o1:
		if o >= i:
			o = o - i
		else:
			ans = ans + 1
	for i in e1:
		if e >= i:
			e = e - i
		else:
			ans = ans + 1
	ans = ans + 2 * (ep + op)
	print(ans)


def main():
	n = int(input())
	lst = list(map(int, input().split()))
	nums = set()
	for el in lst:
		if el != 0:
			nums.add(el)
	odd = 0
	even = 0
	for i in range(1, n + 1):
		if not i in nums:
			if i % 2 == 0:
				even += 1
			else:
				odd += 1
	if n == 1:
		print(0)
		return 0
	emties = []
	st = 0
	started = False
	diff = 0
	for i in range(0, len(lst)):
		if lst[i] == 0 and (not started):
			st = i
			started = True
		elif lst[i] != 0 and started:
			emties.append([st, i])
			started = False
		elif i > 0:
			if lst[i] % 2 != lst[i - 1] % 2:
				diff += 1
	if started:
		emties.append([st, len(lst)])
	emties = sorted(emties, key=lambda x: x[1] - x[0])
	for i in range(len(emties)):
		emties[i][1] -= 1
	odd_removed = []
	even_removed = []
	for empty in emties:
		if empty[0] == 0 and empty[1] == len(lst) - 1:
			print(1)
			return 0
		elif empty[0] == 0:
			if lst[empty[1] + 1] % 2 == 1:
				if odd >= empty[1] - empty[0] + 1:
					odd -= empty[1] - empty[0] + 1
					odd_removed.append(empty[1] - empty[0] + 1)
				else:
					diff += 1
			elif even >= empty[1] - empty[0] + 1:
				even -= empty[1] - empty[0] + 1
				even_removed.append(empty[1] - empty[0] + 1)
			else:
				diff += 1
		elif empty[1] == len(lst) - 1:
			if lst[empty[0] - 1] % 2 == 1:
				if odd >= empty[1] - empty[0] + 1:
					odd -= empty[1] - empty[0] + 1
					odd_removed.append(empty[1] - empty[0] + 1)
				else:
					diff += 1
			elif even >= empty[1] - empty[0] + 1:
				even -= empty[1] - empty[0] + 1
				even_removed.append(empty[1] - empty[0] + 1)
			else:
				diff += 1
		elif lst[empty[0] - 1] % 2 != lst[empty[1] + 1] % 2:
			diff += 1
		elif lst[empty[1] + 1] % 2 == 0:
			if even >= empty[1] - empty[0] + 1:
				even -= empty[1] - empty[0] + 1
			else:
				even_removed = sorted(even_removed)
				if len(even_removed) > 0 and even_removed[-1] + even >= empty[1] - empty[0] + 1:
					diff += 1
					even -= empty[1] - empty[0] + 1 - even_removed[-1]
					even_removed.pop()
				else:
					diff += 2
		elif lst[empty[1] + 1] % 2 == 1:
			if odd >= empty[1] - empty[0] + 1:
				odd -= empty[1] - empty[0] + 1
			else:
				odd_removed = sorted(odd_removed)
				if len(odd_removed) > 0 and odd_removed[-1] + odd >= empty[1] - empty[0] + 1:
					diff += 1
					odd -= empty[1] - empty[0] + 1 - odd_removed[-1]
					odd_removed.pop()
				else:
					diff += 2
	print(diff)
t = 1
for i in range(t):
	main()


N = int(input())
v = [int(x) for x in input().split()]
have = set(v)
dont_have = set(range(1, N + 1)) - have
n_even = len([x for x in dont_have if x % 2 == 0])
n_odd = len(dont_have) - n_even
import functools
INF = 2 ** 20

@functools.lru_cache(maxsize=None)
def rec(idx, even_used, last_even):
	if idx == 0 and even_used == 0:
		return 0
	if idx == 0:
		return INF
	if even_used > n_even:
		return INF
	if even_used < 0:
		return INF
	i = idx - 1
	if v[i] != 0:
		is_even = v[i] % 2 == 0
		if last_even != is_even:
			return INF
		return min(rec(i, even_used, True) + int(not is_even), rec(i, even_used, False) + int(is_even))
	if last_even:
		return min(rec(i, even_used - 1, True), rec(i, even_used - 1, False) + 1)
	else:
		return min(rec(i, even_used, True) + 1, rec(i, even_used, False))
print(min(rec(N, n_even, False), rec(N, n_even, True)))


from sys import stdin, stdout
import gc
gc.disable()
import array

def get_count():
	aux = set(arr)
	(odd, even) = (0, 0)
	for i in range(1, n + 1):
		if i not in aux:
			if i % 2:
				odd += 1
			else:
				even += 1
	return (odd, even)

def pol(num):
	return num % 2

def make(first, second, third, fourth):
	return str(first) + ' ' + str(second) + ' ' + str(third) + ' ' + str(fourth)

def brute(arr, index, odd, even, prev):
	global dp
	if index == n:
		return 0
	if make(index, odd, even, prev) in dp:
		return dp[make(index, odd, even, prev)]
	first = float('inf')
	second = float('inf')
	third = float('inf')
	if index > 0:
		if arr[index] == 0:
			if odd > 0:
				cost = 0
				arr[index] = 1
				if pol(arr[index - 1]) == 0:
					cost = 1
				first = cost + brute(arr, index + 1, odd - 1, even, 1)
			if even > 0:
				cost = 0
				arr[index] = 2
				if pol(arr[index - 1]) == 1:
					cost = 1
				second = cost + brute(arr, index + 1, odd, even - 1, 0)
			arr[index] = 0
		else:
			cost = 0
			if pol(arr[index - 1]) != pol(arr[index]):
				cost = 1
			third = cost + brute(arr, index + 1, odd, even, pol(arr[index]))
	elif arr[index] == 0:
		if odd > 0:
			arr[index] = 1
			first = brute(arr, index + 1, odd - 1, even, 1)
		if even > 0:
			arr[index] = 2
			second = brute(arr, index + 1, odd, even - 1, 0)
		arr[index] = 0
	else:
		third = brute(arr, index + 1, odd, even, pol(arr[index]))
	dp[make(index, odd, even, prev)] = min(first, second, third)
	return min(first, second, third)
n = int(stdin.readline().strip())
arr = list(map(int, stdin.readline().split()))
(odd, even) = get_count()
dp = dict()
print(brute(arr, 0, odd, even, -1))


from functools import lru_cache
N = int(input())
nums = list(map(int, input().strip().split()))

@lru_cache(None)
def dp(a, b, last):
	if a < 0 or b < 0:
		return N
	if a == 0 and b == 0:
		return 0
	i = N - a - b
	if nums[i] != 0:
		bit = nums[i] & 1
		if bit == 0:
			a -= 1
		else:
			b -= 1
		return dp(a, b, bit) + (bit ^ last)
	else:
		return min(dp(a - 1, b, 0) + last, dp(a, b - 1, 1) + 1 - last)
(b, a) = ((N + 1) // 2, N // 2)
print(min(dp(a, b, 0), dp(a, b, 1)))


def main():
	n = int(input())
	p = list(map(int, input().split()))
	s = set(p)
	cnt = [0, 0]
	for i in range(1, n + 1):
		if not i in s:
			cnt[i % 2] += 1
	m = {}

	def eq(a, b):
		if a == b:
			return 0
		else:
			return 1

	def solve(idx, even, odd, prev):
		if idx == n:
			return 0
		ans = 0
		key = (idx, even, odd, prev)
		if key in m:
			return m[key]
		if p[idx] == 0:
			ev = 1000000000.0
			od = 1000000000.0
			if even > 0:
				ev = eq(prev, 0)
				ev += solve(idx + 1, even - 1, odd, 0)
			if odd > 0:
				od = eq(prev, 1)
				od += solve(idx + 1, even, odd - 1, 1)
			ans = min(ev, od)
		else:
			ans = eq(prev, p[idx] % 2)
			ans += solve(idx + 1, even, odd, p[idx] % 2)
		m[key] = ans
		return ans
	(even, odd) = cnt
	print(min(solve(0, even, odd, 0), solve(0, even, odd, 1)))
	return
main()


import sys
n = int(input())
arr = list(map(int, input().split()))
nope = []
for i in range(1, n + 1):
	if i not in arr:
		nope.append(i)
chet = 0
nechet = 0
for i in nope:
	if i % 2 == 0:
		chet += 1
	else:
		nechet += 1
ans = 0
for i in range(n - 1):
	if arr[i] != 0 and arr[i + 1] != 0 and (arr[i] % 2 != arr[i + 1] % 2):
		ans += 1
groups = []
left = -1
right = -1
for i in range(n):
	if arr[i] == 0:
		right = i
		if left == -1:
			left = i
	else:
		if right == -1:
			continue
		if left == 0 or right == n - 1:
			groups.append((-1, left, right))
		elif arr[left - 1] % 2 == arr[right + 1] % 2:
			groups.append((arr[left - 1] % 2, left, right))
		else:
			ans += 1
		left = -1
		right = -1
if right != -1:
	if left == 0 or right == n - 1:
		groups.append((-1, left, right))
	elif arr[left - 1] % 2 == arr[right + 1] % 2:
		groups.append((arr[left - 1] % 2, left, right))
	else:
		ans += 1
groups.sort(key=lambda x: (-x[0], x[2] - x[1]))
for group in groups:
	key = group[0]
	left = group[1]
	right = group[2]
	cost = right - left + 1
	if key == 1:
		if nechet >= cost:
			nechet -= cost
		else:
			ans += 2
	elif key == 0:
		if chet >= cost:
			chet -= cost
		else:
			ans += 2
	else:
		if left == 0 and right == n - 1:
			if left == right:
				print(0)
			else:
				print(1)
			sys.exit()
		if left == 0:
			x = arr[right + 1]
			if x % 2 == 0:
				if chet >= right + 1:
					chet -= right + 1
				else:
					ans += 1
			elif nechet >= right + 1:
				nechet -= right + 1
			else:
				ans += 1
		else:
			x = arr[left - 1]
			if x % 2 == 0:
				if chet >= n - left:
					chet -= n - left
				else:
					ans += 1
			elif nechet >= n - left:
				nechet -= n - left
			else:
				ans += 1
print(ans)


import sys

def fastio():
	from io import StringIO
	from atexit import register
	global input
	sys.stdin = StringIO(sys.stdin.read())
	input = lambda : sys.stdin.readline().rstrip('\r\n')
	sys.stdout = StringIO()
	register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

def debug(*var, sep=' ', end='\n'):
	print(*var, file=sys.stderr, end=end, sep=sep)
INF = 10 ** 20
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br
(n,) = I()
p = I()
s = set(p)
par = [0, 0]
for i in range(1, n + 1):
	if i in s:
		continue
	par[i % 2] += 1

def check(x, y):
	a = [x] + p + [y]
	res = 0
	parity = [[], [], []]
	last = x % 2
	idx = 0
	cur_par = [par[0], 0, par[1]]
	for i in range(1, n + 2):
		if a[i] == 0:
			continue
		if last == -1:
			parity
		if last != -1:
			now = a[i] % 2
			cur = i - idx - 1
			if cur != 0:
				parity[last + now].append(cur)
		last = a[i] % 2
		idx = i
	com = [0, 0, 0]
	for i in range(2, n + 2):
		if a[i] != 0 and a[i - 1] != 0 and (a[i - 1] % 2 ^ a[i] % 2 == 1):
			res += 1
	for i in range(0, 3, 2):
		parity[i].sort()
		for j in parity[i]:
			if j <= cur_par[i]:
				cur_par[i] -= j
				com[i] += 1
			else:
				break
	res += 2 * (len(parity[0]) - com[0] + len(parity[2]) - com[2])
	res += len(parity[1])
	return res
ans = INF
ans = check(4, 1)
ans = min(ans, check(1, 1))
ans = min(ans, check(4, 4))
ans = min(ans, check(1, 4))
print(ans)


n = int(input())
nums = [int(x) for x in input().split()]
missing = set([x for x in range(1, n + 1)])
if nums.count(0) == n:
	if n == 1:
		print(0)
	else:
		print(1)
else:
	for x in nums:
		if x != 0:
			missing.remove(x)
	odds = 0
	evens = 0
	for x in missing:
		if x % 2 == 0:
			evens += 1
		else:
			odds += 1
	gaps = []
	gaps2 = []
	ind = 0
	if nums[0] == 0:
		left = -1
		leftInd = 0
		while nums[ind] == 0:
			ind += 1
		rightInd = ind
		right = nums[ind] % 2
		gaps2.append([rightInd - leftInd, left, right])
	if nums[-1] == 0:
		right = -1
		rightInd = n
		while nums[n - 1] == 0:
			n -= 1
		leftInd = n - 1
		left = nums[n - 1] % 2
		gaps2.append([rightInd - leftInd, left, right])
	while ind < n:
		if nums[ind] == 0:
			left = nums[ind - 1] % 2
			leftInd = ind
			while nums[ind] == 0:
				ind += 1
			rightInd = ind
			right = nums[ind] % 2
			gaps.append([rightInd - leftInd, left, right])
		else:
			ind += 1
	gaps.sort()
	total = 0
	for x in range(n - 1):
		if nums[x] != 0 and nums[x + 1] != 0 and (nums[x] % 2 != nums[x + 1] % 2):
			total += 1
	for x in range(len(gaps) - 1, -1, -1):
		if gaps[x][1] + gaps[x][2] == 1:
			gaps.pop(x)
			total += 1

	def best(gaps, odd, even):
		total = 0
		for (l, ty, ty2) in gaps:
			if ty == 1:
				if odd >= l:
					odd -= l
				else:
					total += 2
			elif even >= l:
				even -= l
			else:
				total += 2
		return total
	first = total + best(gaps, odds, evens) + len(gaps2)
	for x in gaps2:
		if x[1] == 1 or x[2] == 1:
			if odds >= x[0]:
				first = min(first, total + best(gaps, odds - x[0], evens) + len(gaps2) - 1)
		elif evens >= x[0]:
			first = min(first, total + best(gaps, odds, evens - x[0]) + len(gaps2) - 1)
	if len(gaps2) == 2:
		newOdd = odds
		newEven = evens
		if gaps2[0][2] == 1:
			newOdd -= gaps2[0][0]
		else:
			newEven -= gaps2[0][0]
		if gaps2[1][1] == 1:
			newOdd -= gaps2[1][0]
		else:
			newEven -= gaps2[1][0]
		if newOdd >= 0 and newEven >= 0:
			first = min(first, total + best(gaps, newOdd, newEven))
	print(first)


import re

def helper(l):
	s = ''.join(l).replace(' ', '')
	print(s.count('01') + s.count('10'))

def main():
	n = int(input())
	l = ['01'[x & 1] if x else ' ' for x in map(int, input().split())]
	if ' ' not in l:
		return helper(l)
	if l == [' '] * n:
		return print('01'[n > 1])
	(s, shift) = (''.join(l), l[0] != ' ')
	(dd, sp) = (re.findall('\\d+', s), re.findall(' +', s))
	l = [''] * (len(dd) + len(sp))
	l[1 - shift::2] = dd
	l[shift::2] = sp
	gaps = list(range(2 - shift, len(l), 2))
	rshift = l[-1][0] != ' '
	if not rshift:
		del gaps[-1]
	for d in '01':
		cnt = (n + int(d)) // 2 - s.count(d)
		gapsd = [i for i in gaps if l[i - 1][-1] == d == l[i + 1][0]]
		gapsd.sort(key=lambda i: len(l[i]), reverse=True)
		while gapsd and len(l[gapsd[-1]]) <= cnt:
			cnt -= len(l[gapsd[-1]])
			l[gapsd[-1]] = ''
			del gapsd[-1]
		if not shift and l[1][0] == d and (len(l[0]) <= cnt):
			cnt -= len(l[0])
			l[0] = ''
		if not rshift and l[-2][-1] == d and (len(l[-1]) <= cnt):
			cnt -= len(l[0])
			l[-1] = ''
		d = '01'[d == '0']
		for i in gapsd:
			l[i] = d
	if not shift and l[0]:
		l[0] = '01'[l[1][0] == '0']
	if not rshift and l[-1]:
		l[-1] = '01'[l[-2][-1] == '0']
	helper(l)
main()


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]))


import sys
input = sys.stdin.readline
INF = 10 ** 9
n = int(input())
array = [int(item) for item in input().split()]
seen = set(array)
odd_num = 0
eve_num = 0
for i in range(1, n + 1):
	if i not in seen:
		if i % 2 == 0:
			eve_num += 1
		else:
			odd_num += 1
num = odd_num + eve_num
dp = [[[INF] * (num + 2) for _ in range(3)] for _ in range(n + 1)]
dp[0][0][0] = 0
for (i, item) in enumerate(array):
	if item != 0:
		if item % 2 == 0:
			for k in range(odd_num + 1):
				dp[i + 1][2][k] = min(dp[i + 1][2][k], dp[i][2][k])
				dp[i + 1][2][k] = min(dp[i + 1][2][k], dp[i][1][k] + 1)
				dp[i + 1][2][k] = min(dp[i + 1][2][k], dp[i][0][k])
		else:
			for k in range(odd_num + 1):
				dp[i + 1][1][k] = min(dp[i + 1][1][k], dp[i][1][k])
				dp[i + 1][1][k] = min(dp[i + 1][1][k], dp[i][2][k] + 1)
				dp[i + 1][1][k] = min(dp[i + 1][1][k], dp[i][0][k])
	else:
		for k in range(num, -1, -1):
			dp[i + 1][1][k + 1] = min(dp[i + 1][1][k + 1], dp[i][1][k])
			dp[i + 1][1][k + 1] = min(dp[i + 1][1][k + 1], dp[i][2][k] + 1)
			dp[i + 1][1][k + 1] = min(dp[i + 1][1][k + 1], dp[i][0][k])
		for k in range(num, -1, -1):
			dp[i + 1][2][k] = min(dp[i + 1][2][k], dp[i][1][k] + 1)
			dp[i + 1][2][k] = min(dp[i + 1][2][k], dp[i][2][k])
			dp[i + 1][2][k] = min(dp[i + 1][2][k], dp[i][0][k])
print(min(dp[n][1][odd_num], dp[n][2][odd_num]))


n = int(input())
a = list(map(int, input().split()))
if a.count(0) == n:
	if n == 1:
		print(0)
	else:
		print(1)
	exit(0)
chc = [0, 0]
ans = -1
sob = []
curch = -1
cc = 0
isfirst = [-1, 0]
islast = [-1, 0]
for i in range(n):
	if a[i] == 0:
		cc += 1
	elif curch == a[i] % 2:
		if cc != 0:
			sob.append([cc, curch])
		cc = 0
	else:
		if curch == -1 and cc != 0:
			isfirst[0] = a[i] % 2
			isfirst[1] = cc
		ans += 1
		curch = a[i] % 2
		cc = 0
if cc != 0:
	islast[0] = curch % 2
	islast[1] = cc
sob.sort()
for i in range(1, n + 1):
	if i not in a:
		chc[i % 2] += 1
for i in sob:
	if chc[i[1]] >= i[0]:
		chc[i[1]] -= i[0]
	else:
		ans += 2
if isfirst[0] != -1:
	if chc[isfirst[0]] >= isfirst[1]:
		chc[isfirst[0]] -= isfirst[1]
	else:
		ans += 1
if islast[0] != -1:
	if chc[islast[0]] >= islast[1]:
		chc[islast[0]] -= islast[1]
	else:
		ans += 1
print(ans)


n = int(input())
l = list(map(int, input().split()))
a = [0, 0]
for i in range(1, n + 1):
	if i not in l:
		if i % 2 == 0:
			a[0] += 1
		else:
			a[1] += 1
s = -1
e = -1
ind = -1
ans = 0
ind1 = -1
f = n - 1
end = 0
for i in range(n):
	if l[i] != 0:
		f = i
		break
for i in range(n):
	if l[n - 1 - i] != 0:
		end = n - 1 - i
		break
i = f + 1
fsd = [[], []]
while i < end + 1:
	if l[i] == 0 and l[i - 1] == 0:
		i += 1
		continue
	if l[i] != 0 and l[i - 1] != 0:
		i += 1
		continue
	if l[i] == 0 and l[i - 1] != 0:
		s = l[i - 1]
		ind = i - 1
	if l[i] != 0 and l[i - 1] == 0:
		e = l[i]
		ind1 = i
	if ind >= ind1:
		i += 1
		continue
	if s != -1 and e != -1:
		if s % 2 != e % 2:
			ans += 1
		if s % 2 == e % 2:
			fsd[s % 2].append(ind1 - ind - 1)
	i += 1
fsd1 = [[], []]
if f != 0:
	e = l[f]
	fsd1[e % 2].append(f)
if end != n - 1:
	s = l[end]
	fsd1[s % 2].append(n - end - 1)
fsd[0].sort()
fsd[1].sort()
fsd1[0].sort()
fsd1[1].sort()
s = 0
t = 0
for i in range(len(fsd[0])):
	s = s + fsd[0][i]
	if s > a[0]:
		a[0] -= s - fsd[0][i]
		t = 1
		ans += 2 * (len(fsd[0]) - i)
		break
if t == 0:
	a[0] -= sum(fsd[0])
s = 0
t = 0
for i in range(len(fsd[1])):
	s = s + fsd[1][i]
	if s > a[1]:
		a[1] -= s - fsd[1][i]
		t = 1
		ans += 2 * (len(fsd[1]) - i)
		break
if t == 0:
	a[1] -= sum(fsd[1])
s = 0
for i in range(len(fsd1[0])):
	s = s + fsd1[0][i]
	if s > a[0]:
		a[0] -= s - fsd1[0][i]
		t = 1
		ans += 1 * (len(fsd1[0]) - i)
		break
s = 0
for i in range(len(fsd1[1])):
	s = s + fsd1[1][i]
	if s > a[1]:
		a[1] -= s - fsd1[1][i]
		t = 1
		ans += 1 * (len(fsd1[1]) - i)
		break
for i in range(1, n):
	if l[i] != 0 and l[i - 1] != 0 and (l[i - 1] % 2 != l[i] % 2):
		ans += 1
if sum(l) == 0 and n > 1:
	ans = 1
print(ans)


def solve(bulbs, i, ec, oc, prev, memo={}):
	if i == len(bulbs):
		if min(ec, oc) != 0:
			return float('inf')
		return 0
	if bulbs[i] != 0:
		return (prev != bulbs[i] % 2) + solve(bulbs, i + 1, ec, oc, bulbs[i] % 2, memo)
	if (i, ec, oc, prev) not in memo:
		eit = (prev == 1) + solve(bulbs, i + 1, ec - 1, oc, 0, memo)
		oit = (prev == 0) + solve(bulbs, i + 1, ec, oc - 1, 1, memo)
		memo[i, ec, oc, prev] = min(eit, oit)
	return memo[i, ec, oc, prev]
n = int(input())
bulbs = list(map(int, input().split()))
bulbSet = set(bulbs)
(ec, oc) = (0, 0)
for i in range(1, n + 1):
	if i not in bulbSet:
		if i % 2 == 0:
			ec += 1
		else:
			oc += 1
	memo = {}
print(min(solve(bulbs, 0, ec, oc, 0, memo), solve(bulbs, 0, ec, oc, 1, memo)))


n = int(input())
l = list(map(int, input().split()))
dp = []
ans = 0
sp1 = [0, 0]
sp2 = [0, 0]
if n % 2 == 0:
	ev = n // 2
	od = n // 2
else:
	od = 1 + n // 2
	ev = n // 2
a = -1
b = -1
c = 0
for i in range(n - 1):
	if l[i] != 0 and l[i + 1] != 0:
		if l[i] % 2 != l[i + 1] % 2:
			ans += 1
for i in range(n + 1):
	if i == n:
		if l[i - 1] == 0:
			sp2[0] = c
			sp2[1] = a
		break
	if l[i] == 0:
		c += 1
	elif l[i] % 2 == 0:
		b = 0
		ev -= 1
		if c:
			x = [c, a, b]
			if a == -1:
				sp1[0] = c
				sp1[1] = b
			elif b == -1:
				sp2[0] = c
				sp2[1] = a
			else:
				dp.append(x)
		a = 0
		c = 0
		b = -1
	else:
		b = 1
		od -= 1
		if c:
			if a == -1:
				sp1[0] = c
				sp1[1] = b
			elif b == -1:
				sp2[0] = c
				sp2[1] = a
			else:
				x = [c, a, b]
				dp.append(x)
		a = 1
		c = 0
		b = -1
dp = sorted(dp, key=lambda x: x[0])
if n == 1:
	print(0)
	exit()
if od + ev == n:
	print(1)
	exit()
for i in range(len(dp)):
	if dp[i][1] == dp[i][2]:
		if dp[i][1] == 1:
			if od >= dp[i][0]:
				od -= dp[i][0]
			else:
				ans += 2
		elif ev >= dp[i][0]:
			ev -= dp[i][0]
		else:
			ans += 2
	else:
		ans += 1
if sp1[0]:
	if sp1[1] == 1:
		if od >= sp1[0]:
			od -= sp1[0]
		else:
			ans += 1
	elif ev >= sp1[0]:
		ev -= sp1[0]
	else:
		ans += 1
if sp2[0]:
	if sp2[1] == 1:
		if od >= sp2[0]:
			od -= sp2[0]
		else:
			ans += 1
	elif ev >= sp2[0]:
		ev -= sp2[0]
	else:
		ans += 1
print(ans)


n = int(input())
bulb = list(map(int, input().split()))

def complex(n, bulb):
	temp = 0
	for x in range(n - 1):
		if bulb[x] % 2 == 0 and bulb[x + 1] % 2 != 0 and (bulb[x] != 0) and (bulb[x + 1] != 0):
			temp += 1
		elif bulb[x] % 2 != 0 and bulb[x + 1] % 2 == 0 and (bulb[x] != 0) and (bulb[x + 1] != 0):
			temp += 1
	return temp

def compareEvenOrOdd(num, even, odd):
	if num % 2 == 0:
		even -= 1
	else:
		odd -= 1
	return (even, odd)

def cal_complex(temp1, temp2, dic, complexs, k):
	if temp1 - dic >= 0:
		temp1 = temp1 - dic
	else:
		temp2 = temp2 - (dic - temp1)
		temp1 = 0
		complexs = complexs + k
	return (temp1, temp2, complexs)

def sorting(n, bulb):
	even = n // 2
	odd = n - even
	dictsort = {}
	i = 0
	complexs = complex(n, bulb)
	while i < n:
		if bulb[i] != 0 and i < n - 1:
			if bulb[i + 1] == 0:
				dictsort[i] = 0
				(even, odd) = compareEvenOrOdd(bulb[i], even, odd)
				j = i
				i += 1
				while i < n and bulb[i] == 0:
					dictsort[j] += 1
					i += 1
			else:
				(even, odd) = compareEvenOrOdd(bulb[i], even, odd)
				i += 1
		elif bulb[i] != 0:
			(even, odd) = compareEvenOrOdd(bulb[i], even, odd)
			i += 1
		elif bulb[0] == 0:
			dictsort[0] = 1
			j = i
			i += 1
			while i < n and bulb[i] == 0:
				dictsort[j] += 1
				i += 1
	dictsort = sorted(dictsort.items(), key=lambda x: x[1])
	specialodd = []
	specialeven = []
	if len(dictsort) > 0 and dictsort[0][1] == n and (n > 1):
		print(1)
	elif n <= 1:
		print(0)
	else:
		for i in range(len(dictsort)):
			first = dictsort[i][0]
			last = dictsort[i][0] + dictsort[i][1] + 1
			if bulb[first] != 0 and last < n:
				if bulb[first] % 2 == 0 and bulb[last] % 2 == 0:
					if even - dictsort[i][1] < 0 and len(specialeven) > 0:
						(even, odd, complexs) = cal_complex(even, odd, specialeven[0][1], complexs, 1)
						specialeven.remove(specialeven[0])
					(even, odd, complexs) = cal_complex(even, odd, dictsort[i][1], complexs, 2)
				elif bulb[first] % 2 != 0 and bulb[last] % 2 != 0:
					if odd - dictsort[i][1] < 0 and len(specialodd) > 0:
						(odd, even, complexs) = cal_complex(odd, even, specialodd[0][1], complexs, 1)
						specialodd.remove(specialodd[0])
					(odd, even, complexs) = cal_complex(odd, even, dictsort[i][1], complexs, 2)
				else:
					complexs = complexs + 1
			elif bulb[first] == 0:
				if bulb[last - 1] % 2 == 0:
					specialeven.append(dictsort[i])
				else:
					specialodd.append(dictsort[i])
			elif bulb[first] % 2 == 0:
				specialeven.append(dictsort[i])
			else:
				specialodd.append(dictsort[i])
		for x in specialodd:
			(odd, even, complexs) = cal_complex(odd, even, x[1], complexs, 1)
		for x in specialeven:
			(even, odd, complexs) = cal_complex(even, odd, x[1], complexs, 1)
		print(complexs)
sorting(n, bulb)


import sys
input = sys.stdin.readline
n = int(input())
p = list(map(int, input().split()))

def maxDiff(p, n):
	if n == 1:
		return 0
	used = {i for i in p}
	rest = {0: 0, 1: 0}
	for i in range(1, n + 1):
		if i not in used:
			rest[i % 2] += 1
	A00 = []
	A11 = []
	A01 = 0
	prev = -1
	start = -1
	for (i, el) in enumerate(p):
		if el == 0 and prev > 0:
			le = i
			start = prev
		elif el > 0 and prev == 0 and (start > 0):
			start %= 2
			end = el % 2
			if start > 0 and end > 0:
				A11.append(i - le)
			elif not (start > 0 or end > 0):
				A00.append(i - le)
			else:
				A01 += 1
		prev = el
	start = 0
	for el in p:
		if el > 0:
			break
		start += 1
	if start == n:
		return 1
	end = 0
	for el in p[::-1]:
		if el > 0:
			break
		end += 1
	A00.sort(reverse=True)
	A11.sort(reverse=True)
	while A00:
		sect = A00.pop()
		if rest[0] < sect:
			A00.append(sect)
			break
		rest[0] -= sect
	while A11:
		sect = A11.pop()
		if rest[1] < sect:
			A11.append(sect)
			break
		rest[1] -= sect
	ans = A01
	ans += 2 * len(A00)
	ans += 2 * len(A11)
	prev = p[0]
	for el in p[1:]:
		if el > 0 and prev > 0 and ((el + prev) % 2 > 0):
			ans += 1
		prev = el
	sOdd = p[start] % 2
	if rest[sOdd] < start:
		ans += 1
	else:
		rest[sOdd] -= start
	eOdd = p[-end - 1] % 2
	if rest[eOdd] < end:
		ans += 1
	else:
		rest[eOdd] -= end
	return ans
ans = maxDiff(p, n)
print(ans)


import sys

def updiv(x, y):
	if x % y == 0:
		return x // y
	else:
		return x // y + 1
n = int(input())
p = list(map(int, input().split()))
if n == 1:
	print(0)
	sys.exit()
o = updiv(n, 2)
e = n // 2
for i in range(n):
	if p[i] > 0 and p[i] % 2 == 0:
		e -= 1
		p[i] = 2
	elif p[i] > 0 and p[i] % 2 == 1:
		o -= 1
		p[i] = 1
ans = 0
for i in range(n - 1):
	if p[i] == 1 and p[i + 1] == 2 or (p[i] == 2 and p[i + 1] == 1):
		ans += 1
flag = False
p.append(float('inf'))
oddone = []
eveone = []
inodd = []
ineve = []
for i in range(n + 1):
	if not flag and p[i] == 0:
		l = i
		flag = True
	if flag and p[i] != 0:
		r = i
		if l == 0:
			if p[r] == 1:
				oddone.append(r - l)
			else:
				eveone.append(r - l)
		elif r == n:
			if p[l - 1] == 1:
				oddone.append(r - l)
			else:
				eveone.append(r - l)
		elif p[l - 1] == 1 and p[r] == 1:
			inodd.append(r - l)
		elif p[l - 1] == 2 and p[r] == 2:
			ineve.append(r - l)
		else:
			ans += 1
		flag = False
ableodd = len(inodd) * 2 + len(oddone)
ableeve = len(ineve) * 2 + len(eveone)
inodd.sort()
ineve.sort()
oddone.sort()
eveone.sort()
for i in range(len(inodd)):
	if o >= inodd[i]:
		o -= inodd[i]
		ableodd -= 2
	else:
		break
for i in range(len(oddone)):
	if o >= oddone[i]:
		o -= oddone[i]
		ableodd -= 1
	else:
		break
for i in range(len(ineve)):
	if e >= ineve[i]:
		e -= ineve[i]
		ableeve -= 2
	else:
		break
for i in range(len(eveone)):
	if e >= eveone[i]:
		e -= eveone[i]
		ableeve -= 1
	else:
		break
print(ans + ableodd + ableeve)


n = int(input())
a = input().split(' ')
a = [int(a[i]) for i in range(n)]

def calcHoleStranges(holes, m, pen1=True):
	if m < 0:
		return n
	result = 0
	if pen1:
		holes_pen1 = [h for h in holes if h[1] == 1]
		if len(holes_pen1) == 1:
			hole = holes_pen1[0]
			result = min(1 + calcHoleStranges(holes, m, pen1=False), calcHoleStranges(holes, m - hole[0], pen1=False))
			return result
		if len(holes_pen1) == 2:
			hole1 = holes_pen1[0]
			hole2 = holes_pen1[1]
			result = min(2 + calcHoleStranges(holes, m, pen1=False), 1 + calcHoleStranges(holes, m - min(hole1[0], hole2[0]), pen1=False), calcHoleStranges(holes, m - hole1[0] - hole2[0], pen1=False))
			return result
		return calcHoleStranges(holes, m, pen1=False)
	else:
		holes = [h for h in holes if h[1] == 2]
		holes.sort()
		for h in holes:
			m -= h[0]
			if m < 0:
				result += 2
		return result

def getStranges(a):
	if n % 2 == 0:
		odds = n / 2
		evens = n / 2
	else:
		odds = (n + 1) / 2
		evens = (n - 1) / 2
	for x in a:
		if x == 0:
			continue
		if x % 2 == 0:
			evens -= 1
		else:
			odds -= 1
	if odds + evens == n:
		if n == 1:
			return 0
		return 1
	odd_holes = list()
	even_holes = list()
	stranges = 0
	length = 0
	left_bound = None
	for (i, x) in enumerate(a):
		if x != 0:
			if left_bound is not None:
				pen = 2
				if left_bound % 2 != x % 2:
					stranges += 1
					left_bound = x
					length = 0
					continue
			else:
				pen = 1
			if length > 0:
				if x % 2 == 0:
					even_holes.append((length, pen))
				else:
					odd_holes.append((length, pen))
				length = 0
			left_bound = x
		else:
			length += 1
			if i == len(a) - 1:
				if left_bound % 2 == 0:
					even_holes.append((length, 1))
				else:
					odd_holes.append((length, 1))
	need_even = sum((e[0] for e in even_holes))
	need_odd = sum((o[0] for o in odd_holes))
	if need_even > evens:
		stranges += calcHoleStranges(even_holes, evens)
	elif need_odd > odds:
		stranges += calcHoleStranges(odd_holes, odds)
	return stranges

def bruteForse(a):
	result = n
	no_numbers = set(range(1, n + 1)) - set(a)
	if len(no_numbers) == 0:
		result = 0
		for i in range(n - 1):
			if a[i] % 2 != a[i + 1] % 2:
				result += 1
		return result
	a = a.copy()
	for i in range(n):
		if a[i] == 0:
			for x in no_numbers:
				a[i] = x
				result = min(result, bruteForse(a))
			break
	return result

def getAllTasks(a):
	result = []
	no_numbers = set(range(n + 1)) - (set(a) - {0})
	a = a.copy()
	for i in range(n):
		if a[i] == -1:
			for x in no_numbers:
				a[i] = x
				result.extend(getAllTasks(a))
			break
	else:
		result.append(a)
	return result

def test(k):
	listA = list()
	a = [-1 for _ in range(k)]
	listA = getAllTasks(a)
	for a in listA:
		if getStranges(a) != bruteForse(a):
			print(a, getStranges(a), bruteForse(a))
print(getStranges(a))


def garland(a):
	n = len(a)
	a = [0] + a
	oo = n + 1
	dp = [[[oo, oo] for __ in range(n + 1)] for _ in range(n + 1)]
	dp[0][0][0] = dp[0][0][1] = 0
	for i in range(1, n + 1):
		for j in range(i + 1):
			if a[i] % 2 == 1 or a[i] == 0:
				dp[i][j][1] = min(dp[i - 1][j][0] + 1, dp[i - 1][j][1])
			if a[i] % 2 == 0 and j > 0:
				dp[i][j][0] = min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1] + 1)
	m = int(n / 2)
	return min(dp[n][m])
c1 = int(input())
c2 = str(input()).split()
a = []
for i in range(c1):
	a.append(int(c2[i]))
print(garland(a))


import sys
input = sys.stdin.readline
INF = 10 ** 14
N = int(input())
A = list(map(int, input().split()))
odds = (N + 1) // 2
evens = N // 2
for a in A:
	if a == 0:
		continue
	if a % 2 == 0:
		evens -= 1
	else:
		odds -= 1
dp = [[[[INF, INF] for _ in range(odds + 1)] for _ in range(evens + 1)] for _ in range(N + 1)]
dp[0][0][0][0] = 0
dp[0][0][0][1] = 0
for (i, a) in enumerate(A):
	for j in range(evens + 1):
		for k in range(odds + 1):
			if a == 0:
				if k != odds:
					dp[i + 1][j][k + 1][1] = min(dp[i][j][k][0] + 1, dp[i][j][k][1])
				if j != evens:
					dp[i + 1][j + 1][k][0] = min(dp[i][j][k][1] + 1, dp[i][j][k][0])
			elif a % 2 == 0:
				dp[i + 1][j][k][0] = min(dp[i][j][k][1] + 1, dp[i][j][k][0])
			else:
				dp[i + 1][j][k][1] = min(dp[i][j][k][0] + 1, dp[i][j][k][1])
print(min(dp[N][evens][odds]))


n = int(input())
a = list(map(int, input().split()))
s = set(a)
rem_parity = [0, 0]
for i in range(1, n + 1):
	if i not in s:
		rem_parity[i % 2] += 1
inf = 10 ** 9
dp = [[[inf] * 2 for _ in range(n)] for _ in range(n)]
rem = rem_parity[0] + rem_parity[1]
if a[0] != 0:
	dp[0][rem_parity[0]][a[0] % 2] = 0
else:
	if rem_parity[0] > 0:
		dp[0][rem_parity[0] - 1][0] = 0
	if rem_parity[1] > 0:
		dp[0][rem_parity[0]][1] = 0
	rem -= 1
for (i, x) in enumerate(a[1:]):
	if x > 0:
		par = x % 2
		for j in range(n):
			for k in range(2):
				dp[i + 1][j][par] = min(dp[i + 1][j][par], dp[i][j][k] + (k + par) % 2)
	else:
		rem -= 1
		for j in range(n):
			for k in range(2):
				if j > 0:
					dp[i + 1][j - 1][0] = min(dp[i + 1][j - 1][0], dp[i][j][k] + (0 if k == 0 else 1))
				if j <= rem:
					dp[i + 1][j][1] = min(dp[i + 1][j][1], dp[i][j][k] + (0 if k == 1 else 1))
print(min(dp[-1][0]))


import os, sys
from io import BytesIO, IOBase
from math import inf

def main():
	n = int(input())
	p = list(map(int, input().split()))
	eve = n // 2
	for i in p:
		if i:
			eve -= i % 2 ^ 1
	dp = [[[inf, inf] for _ in range(eve + 1)] for _ in range(n + 1)]
	dp[0][-1] = [0, 0]
	for i in range(n):
		if p[i]:
			r = p[i] % 2
			for x in range(eve + 1):
				dp[i + 1][x][r] = min(dp[i][x][r ^ 1] + 1, dp[i][x][r])
		else:
			for x in range(eve):
				dp[i + 1][x][0] = min(dp[i][x + 1][1] + 1, dp[i][x + 1][0])
			for x in range(eve + 1):
				dp[i + 1][x][1] = min(dp[i][x][1], dp[i][x][0] + 1)
	if p[-1]:
		print(dp[-1][0][p[-1] % 2])
	else:
		print(min(dp[-1][0]))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def answer(A, odd, even):
	odds = []
	evens = []
	waseven = 1
	wasodd = 1
	waszero = -1
	ans = 0
	for i in range(len(A)):
		if A[i] and (not A[i] % 2):
			if waszero >= 0 and waseven:
				evens.append(i - waszero)
				waszero = -1
			elif waszero >= 0 and wasodd:
				ans += 1
				waszero = -1
			waseven = 1
			wasodd = 0
		elif A[i]:
			if waszero >= 0 and wasodd:
				odds.append(i - waszero)
				waszero = -1
			elif waszero >= 0 and waseven:
				ans += 1
				waszero = -1
			wasodd = 1
			waseven = 0
		elif waszero == -1:
			waszero = i
	odds.sort()
	evens.sort()
	ans += 2 * len(odds) + 2 * len(evens)
	for el in odds:
		if odd >= el:
			odd -= el
			ans -= 2
		else:
			break
	for el in evens:
		if even >= el:
			even -= el
			ans -= 2
		else:
			break
	for i in range(len(A) - 1):
		if A[i] and A[i + 1] and (A[i] % 2 != A[i + 1] % 2):
			ans += 1
	return ans
n = int(input())
A = list(map(int, input().split()))
odd = n // 2 + n % 2
even = n // 2
for i in range(n):
	if not A[i] % 2 and A[i]:
		even -= 1
	elif A[i]:
		odd -= 1
print(min(answer([1] + A + [1], odd, even), answer([1] + A + [2], odd, even), answer([2] + A + [1], odd, even), answer([2] + A + [2], odd, even)))


INF = 1000

def mod2(a, n):
	(even, odd) = (0, 0)
	for i in range(n):
		if a[i] == 0:
			a[i] = -1
		elif a[i] & 1:
			a[i] = 1
			odd += 1
		else:
			a[i] = 0
			even += 1
	even = n // 2 - even
	odd = (n - 1) // 2 + 1 - odd
	return (even, odd)

def minc(i, e, o, l):
	if i >= n:
		return 0
	cur = dp[i][e][o][l]
	if cur != -1:
		return cur
	if a[i] == 0:
		cur = (0 ^ l) + minc(i + 1, e, o, 0)
	elif a[i] == 1:
		cur = (1 ^ l) + minc(i + 1, e, o, 1)
	else:
		cur = INF
		if e > 0:
			cur = min(cur, (0 ^ l) + minc(i + 1, e - 1, o, 0))
		if o > 0:
			cur = min(cur, (1 ^ l) + minc(i + 1, e, o - 1, 1))
	dp[i][e][o][l] = cur
	return cur
n = int(input())
a = list(map(int, input().split()))
(even, odd) = mod2(a, n)
dp = [[[[-1 for i0 in range(2)] for i1 in range(odd + 1)] for i2 in range(even + 1)] for i3 in range(n)]
if a[0] == 0:
	ans = minc(1, even, odd, 0)
elif a[0] == 1:
	ans = minc(1, even, odd, 1)
else:
	ans = INF
	if even > 0:
		ans = min(ans, minc(1, even - 1, odd, 0))
	if odd > 0:
		ans = min(ans, minc(1, even, odd - 1, 1))
print(ans)


n = int(input())
nums = list(map(int, input().split(' ')))
if n == 1:
	print(0)
	exit()
memory = {}

def dp(i, j, k):
	if i < k - 1:
		return 100
	if i < 0:
		if j == 1 and k != 0 or (j == 0 and k != -1):
			return 100
		else:
			return 0
	if nums[i] != 0:
		if nums[i] % 2 != j:
			return 100
		if j == 0:
			return min(dp(i - 1, 0, k - 1), dp(i - 1, 1, k) + 1)
		else:
			return min(dp(i - 1, 0, k - 1) + 1, dp(i - 1, 1, k))
	if (i, j, k) in memory:
		return memory[i, j, k]
	if j == 0:
		res = min(dp(i - 1, 0, k - 1), dp(i - 1, 1, k) + 1)
	else:
		res = min(dp(i - 1, 0, k - 1) + 1, dp(i - 1, 1, k))
	memory.setdefault((i, j, k), res)
	return res
res = min(dp(n - 1, 0, (n >> 1) - 1), dp(n - 1, 1, n >> 1))
print(res)


from math import inf
import functools
n = int(input())
P = list(map(int, input().split()))
EVEN = n // 2
ODD = n - n // 2
for x in P:
	if x == 0:
		continue
	if x % 2:
		ODD -= 1
	else:
		EVEN -= 1

@functools.lru_cache(None)
def f(i, e, o, p):
	if e < 0:
		return inf
	if o < 0:
		return inf
	if i == n:
		return 0
	if P[i] != 0:
		if P[i] % 2 != p:
			return inf
		case1 = f(i + 1, e, o, p)
		case2 = f(i + 1, e, o, (p + 1) % 2) + int(i + 1 < n)
		return min(case1, case2)
	if p:
		o -= 1
	else:
		e -= 1
	case1 = f(i + 1, e, o, p)
	case2 = f(i + 1, e, o, (p + 1) % 2) + int(i + 1 < n)
	return min(case1, case2)
ans = min(f(0, EVEN, ODD, 0), f(0, EVEN, ODD, 1))
print(ans)


n = int(input())
ps0 = [int(x) for x in input().split()]
to_add = [x for x in range(1, n + 1) if x not in ps0]
if all((x == 0 for x in ps0)):
	if n == 1:
		print(0)
		exit()
	print(1)
	exit()
ANS = 1000
for I in range(2):
	ps = ps0[:]
	if I == 0:
		to_add.sort(key=lambda x: x % 2)
	else:
		to_add.sort(key=lambda x: x % 2, reverse=True)
	odds = [x % 2 for x in to_add].count(1)
	evens = len(to_add) - odds
	for t in to_add:
		so = (101, None)
		se = (101, None)
		so2 = (101, None, None)
		se2 = (101, None, None)
		mixed = None
		left = None
		zero_count = 0
		for (i, p) in enumerate(ps):
			if p == 0:
				zero_count += 1
			else:
				if zero_count > 0:
					if left is None:
						if p % 2 == 0:
							se2 = (zero_count, i - 1, 0)
						else:
							so2 = (zero_count, i - 1, 0)
					elif p % 2 == 0:
						if ps[left] % 2 == 0:
							se = min(se, (zero_count, left + 1))
						else:
							mixed = (i - 1, left + 1)
					elif ps[left] % 2 == 0:
						mixed = (left + 1, i - 1)
					else:
						so = min(so, (zero_count, left + 1))
					zero_count = 0
				left = i
		if zero_count > 0:
			if ps[left] % 2 == 0:
				se2 = min(se2, (zero_count, left + 1, -1))
			else:
				so2 = min(so2, (zero_count, left + 1, -1))
		if t % 2 == 0:
			if se[1] is not None and evens >= se[0]:
				ps[se[1]] = t
			elif se2[1] is not None:
				ps[se2[1]] = t
			elif se[1] is not None and evens < se[0]:
				ps[se[1]] = t
			elif mixed is not None:
				ps[mixed[0]] = t
			elif so2[1] is not None:
				ps[so2[2]] = t
			else:
				ps[so[1]] = t
			evens -= 1
		else:
			if so[1] is not None and odds >= so[0]:
				ps[so[1]] = t
			elif so2[1] is not None:
				ps[so2[1]] = t
			elif so[1] is not None and odds < so[1]:
				ps[so[1]] = t
			elif mixed is not None:
				ps[mixed[1]] = t
			elif se2[1] is not None:
				ps[se2[2]] = t
			else:
				ps[se[1]] = t
			odds -= 1
	ans = 0
	l = None
	for i in range(len(ps)):
		if i == 0:
			continue
		if ps[i] % 2 != ps[i - 1] % 2:
			ans += 1
	ANS = min(ANS, ans)
print(ANS)


n = int(input())
ps = list(map(int, input().split()))
used = [False] * (n + 1)
all_zeros = True
for p in ps:
	used[p] = True
	if p > 0:
		all_zeros = False
if all_zeros:
	if n == 1:
		print(0)
	else:
		print(1)
else:
	start_i = 0
	while ps[start_i] == 0:
		start_i += 1
	starter = ps[start_i]
	end_i = 0
	while ps[n - 1 - end_i] == 0:
		end_i += 1
	last = ps[n - 1 - end_i]
	end_i = n - 1 - end_i
	holes = [[], [], [], []]
	hole_l = 0
	hole_s = start_i
	for i in range(start_i, end_i + 1):
		if ps[i] == 0:
			hole_l += 1
		else:
			if hole_l > 0:
				if ps[i] % 2 == ps[hole_s] % 2:
					holes[ps[hole_s] % 2].append([hole_l, hole_s, i])
			hole_s = i
			hole_l = 0
	if start_i > 0:
		holes[2 + ps[start_i] % 2].append([start_i, -1, start_i])
	if end_i < n - 1:
		holes[2 + ps[end_i] % 2].append([n - end_i - 1, end_i, n])
	unused = [0, 0]
	for i in range(1, n + 1):
		if not used[i]:
			unused[i % 2] += 1
	for i in range(4):
		holes[i].sort()
	for hole_group in range(4):
		if holes[hole_group]:
			while unused[hole_group % 2] >= holes[hole_group][0][0]:
				unused[hole_group % 2] -= holes[hole_group][0][0]
				for i in range(holes[hole_group][0][1] + 1, holes[hole_group][0][2]):
					ps[i] = 1000 + hole_group
				holes[hole_group].pop(0)
				if not holes[hole_group]:
					break
	for even_part_hole in holes[2]:
		for i in range(even_part_hole[1] + 1, even_part_hole[2]):
			ps[i] = 2000 + 1
	for even_part_hole in holes[0]:
		for i in range(even_part_hole[1] + 1, even_part_hole[2]):
			ps[i] = 2000 + 1
	oe = ps[0] % 2
	sol = 0
	for p in ps:
		if p % 2 != oe:
			sol += 1
			oe = p % 2
	print(sol)


import sys
from bisect import bisect
input = sys.stdin.readline
n = int(input())
a2 = list(map(int, input().split()))
s = set(range(1, n + 1))
for x in a2:
	if x > 0:
		s.remove(x)
zerosx = 0
onesx = 0
for num in s:
	if num % 2 == 0:
		zerosx += 1
	else:
		onesx += 1
if n == 1:
	print(0)
elif zerosx + onesx == n:
	print(1)
else:
	sss = []
	c0 = 0
	first = True
	firstparity = 0
	firstcount = 0
	for x in a2:
		if x == 0:
			c0 += 1
		else:
			if first:
				first = False
				firstcount = c0
				firstparity = x % 2
			else:
				sss.append([c0, last, x % 2])
			c0 = 0
			last = x % 2
	ende = c0
	endparity = last
	dastezz = []
	dasteff = []
	dastezf = []
	for el in sss:
		if el[0] > 0:
			if el[1] == el[2]:
				if el[1] == 1:
					dasteff.append(el[0])
				else:
					dastezz.append(el[0])
			else:
				dastezf.append(el[0])
	dastezz.sort()
	dasteff.sort()
	penalty = 0
	for xxx in dastezz:
		if xxx <= zerosx:
			zerosx -= xxx
		else:
			penalty += 2
	for xxx in dasteff:
		if xxx <= onesx:
			onesx -= xxx
		else:
			penalty += 2
	for xxx in dastezf:
		penalty += 1
	if endparity == 1:
		if onesx >= ende:
			onesx -= ende
		else:
			penalty += 1
	elif zerosx >= ende:
		zerosx -= ende
	else:
		penalty += 1
	if firstparity == 1:
		if onesx >= firstcount:
			onesx -= firstcount
		else:
			penalty += 1
	elif zerosx >= firstcount:
		zerosx -= firstcount
	else:
		penalty += 1
	for zz in range(1, n):
		if a2[zz] > 0 and a2[zz - 1] > 0:
			if a2[zz] % 2 != a2[zz - 1] % 2:
				penalty += 1
	print(penalty)


n = int(input())
a = list(map(int, input().split()))
if n == 1:
	print(0)
	exit(0)
dp = [[[10 ** 9, 10 ** 9] for i in range(n + 1)] for j in range(n + 1)]
dp[0][0][0] = 0
dp[0][0][1] = 0
(even, odd) = (0, 0)
for i in range(1, n + 1):
	for j in range(1, n + 1):
		if a[i - 1] == 0 or a[i - 1] % 2:
			dp[i][j][0] = min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1] + 1)
	for j in range(n + 1):
		if a[i - 1] == 0 or not a[i - 1] % 2:
			dp[i][j][1] = min(dp[i - 1][j][0] + 1, dp[i - 1][j][1])
if a[-1] == 0:
	print(min(dp[n][n - n // 2][0], dp[n][n - n // 2][1]))
elif a[-1] % 2:
	print(dp[n][n - n // 2][0])
else:
	print(dp[n][n - n // 2][1])


n = int(input())
p = list(map(int, input().split()))
o = (n + 1) // 2
e = n // 2
for i in range(n):
	if p[i]:
		p[i] %= 2
		if p[i]:
			o -= 1
		else:
			e -= 1
	else:
		p[i] = -1
l = []
if 0 not in p and 1 not in p:
	if n > 1:
		print(1)
	else:
		print(0)
else:
	ans = 0
	for i in range(1, n):
		if p[i] != -1 and p[i - 1] != -1:
			ans += p[i] != p[i - 1]
	while o:
		l = -1
		r = -1
		fl = -1
		fr = n + 1
		for i in range(1, n - 1):
			(l, r) = (-1, -1)
			if p[i] == -1 and p[i - 1] == 1:
				l = i
				for j in range(i, n):
					if p[j] != -1:
						if p[j] == 1:
							r = j - 1
						break
			if r != -1 and r - l <= fr - fl:
				fl = l
				fr = r
		if fl != -1:
			k = min(fr - fl + 1, o)
			if fr - fl + 1 - k:
				break
			for j in range(fl, fr + 1):
				p[j] = 0
			o -= k
		else:
			break
	while e:
		l = -1
		r = -1
		fl = -1
		fr = n + 1
		for i in range(1, n):
			(l, r) = (-1, -1)
			if p[i] == -1 and p[i - 1] == 0:
				l = i
				for j in range(i, n):
					if p[j] != -1:
						if p[j] == 0:
							r = j - 1
						break
			if r != -1 and r - l <= fr - fl:
				fl = l
				fr = r
		if fl != -1:
			k = min(fr - fl + 1, e)
			if fr - fl + 1 - k:
				break
			for i in range(fl, fr + 1):
				p[i] = 0
			e -= k
		else:
			break
	if p[0] == -1:
		i = 0
		while i < n and p[i] == -1:
			p[i] = 0
			i += 1
		if p[i] == 0 and e >= i or (p[i] == 1 and o >= i):
			if p[i] == 0:
				e -= i
			if p[i]:
				o -= i
		else:
			ans += 1
	if p[-1] == -1:
		i = n - 1
		while i and p[i] == -1:
			p[i] = 0
			i -= 1
		if p[i] == 0 and e >= n - i - 1 or (p[i] == 1 and o >= n - i - 1):
			if p[i] == 0:
				e -= n - i - 1
			if p[i]:
				o -= n - i - 1
		else:
			ans += 1
	for i in range(1, n - 1):
		r = -1
		if p[i] == -1 and p[i - 1] != -1:
			for j in range(i, n):
				if p[j] != -1:
					r = p[j]
					break
		if r != -1:
			if r == p[i - 1]:
				ans += 2
			else:
				ans += 1
	print(ans)


from collections import Counter
n = int(input())
pl = list(map(int, input().split()))[:n]
al = set(range(1, n + 1))
rem = al - set(pl)
odds = Counter([k % 2 for k in rem])
if n == 1:
	print(0)
elif max(pl) <= 1:
	print(1)
else:
	res = 0
	i = 0
	groups = []
	bgroups = []
	while i < n and pl[i] == 0:
		i += 1
	if i > 0:
		bgroups.append((pl[i] % 2, i))
	while i < n:
		while i + 1 < n and pl[i + 1] != 0:
			res += (pl[i] + pl[i + 1]) % 2
			i += 1
		if i + 1 < n:
			start = pl[i]
		else:
			break
		i += 1
		curgrouplen = 0
		while i < n and pl[i] == 0:
			i += 1
			curgrouplen += 1
		if i < n:
			finish = pl[i]
			if (start + finish) % 2:
				res += 1
			else:
				groups.append((start % 2, curgrouplen))
		else:
			bgroups.append((start % 2, curgrouplen))
	for (od, ln) in sorted(groups, key=lambda x: x[1]):
		if odds[od] >= ln:
			odds[od] -= ln
		else:
			res += 2
	for (od, ln) in sorted(bgroups, key=lambda x: x[1]):
		if odds[od] >= ln:
			odds[od] -= ln
		else:
			res += 1
	print(res)


import io
import os
from collections import Counter, defaultdict, deque
from functools import lru_cache
inf = float('inf')

def solve(N, A):

	@lru_cache(maxsize=None)
	def dp(i, evensLeft, oddsLeft, last):
		if evensLeft < 0 or oddsLeft < 0:
			return inf
		ret = None
		assert A[i] in [-1, 0, 1]
		if A[i] != -1:
			if A[i] == last:
				if i == 0:
					assert evensLeft == 0 and oddsLeft == 0
					ret = 0
				elif last == 0:
					ret = min(dp(i - 1, evensLeft, oddsLeft, 0), dp(i - 1, evensLeft, oddsLeft, 1) + 1)
				else:
					assert last == 1
					ret = min(dp(i - 1, evensLeft, oddsLeft, 0) + 1, dp(i - 1, evensLeft, oddsLeft, 1))
			else:
				ret = inf
		elif i == 0:
			if last == 0:
				if evensLeft == 1 and oddsLeft == 0:
					ret = 0
				else:
					ret = inf
			elif evensLeft == 0 and oddsLeft == 1:
				ret = 0
			else:
				ret = inf
		elif last == 0:
			ret = min(dp(i - 1, evensLeft - 1, oddsLeft, 0), dp(i - 1, evensLeft - 1, oddsLeft, 1) + 1)
		else:
			assert last == 1
			ret = min(dp(i - 1, evensLeft, oddsLeft - 1, 0) + 1, dp(i - 1, evensLeft, oddsLeft - 1, 1))
		return ret
	A = [x % 2 if x != 0 else -1 for x in A]
	freq = Counter(A)
	evensLeft = N // 2 - freq[0]
	oddsLeft = (N + 1) // 2 - freq[1]
	return min(dp(N - 1, evensLeft, oddsLeft, 0), dp(N - 1, evensLeft, oddsLeft, 1))
if False:
	A = [0, 0, 0, 2, 1]
	print(solve(len(A), A))
	exit()
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = solve(N, A)
print(ans)


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):
				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
				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])
				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
main()


import threading
import sys
from sys import stdin
input = stdin.readline
sys.setrecursionlimit(10 ** 8)
from collections import defaultdict

def main():
	from functools import lru_cache
	n = int(input())
	arr = list(map(int, input().split()))
	odd = 0
	even = 0
	for (i, el) in enumerate(arr):
		if el % 2:
			odd += 1
		else:
			even += 1
	odd = n // 2 + n % 2 - odd
	even = n // 2 - even

	@lru_cache(None)
	def solve(i, o, prev):
		if o < 0:
			return float('inf')
		if i == n:
			if o:
				return float('inf')
			else:
				return 0
		else:
			if prev == None:
				if arr[i] != 0:
					ans = solve(i + 1, o, arr[i] % 2)
				else:
					ans = min(solve(i + 1, o - 1, 1), solve(i + 1, o, 0))
			elif arr[i] != 0:
				ans = int(prev != arr[i] % 2) + solve(i + 1, o, arr[i] % 2)
			else:
				ans = min(int(prev != 1) + solve(i + 1, o - 1, 1), int(prev != 0) + solve(i + 1, o, 0))
			return ans
	print(solve(0, odd, None))
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
from math import *
from collections import defaultdict as dd, deque

def data():
	return sys.stdin.readline().strip()

def mdata():
	return map(int, data().split())
mod = int(1000000000.0 + 7)
n = int(data())
P = list(mdata())
o1 = n // 2 + n % 2
e1 = n // 2
if n == 1:
	print(0)
	exit()
for i in P:
	if i != 0:
		if i % 2 == 0:
			e1 -= 1
		else:
			o1 -= 1
e = []
o = []
ind = 0
while ind < n:
	if P[ind] != 0:
		break
	ind += 1
if ind == n:
	print(1)
	exit()
s = ind
cnt = 0
for i in range(ind + 1, n):
	if P[i] != 0:
		if (P[i] + P[ind]) % 2 == 0:
			if P[i] % 2 == 0:
				e.append(i - ind - 1)
			else:
				o.append(i - ind - 1)
		else:
			cnt += 1
		ind = i
e.sort()
o.sort()
for i in range(len(e)):
	if e[i] <= e1:
		e1 -= e[i]
	else:
		cnt += 2 * (len(e) - i)
for i in range(len(o)):
	if o[i] <= o1:
		o1 -= o[i]
	else:
		cnt += 2 * (len(o) - i)
		break
if P[s] % 2 == 0:
	if e1 < s:
		cnt += 1
	else:
		e1 -= s
elif o1 < s:
	cnt += 1
else:
	o1 -= s
if P[ind] % 2 == 0:
	if e1 < n - 1 - ind:
		cnt += 1
elif o1 < n - 1 - ind:
	cnt += 1
print(cnt)


import functools
n = int(input())

def f(x):
	x = int(x)
	if x == 0:
		return -1
	return x % 2
ps = [f(x) for x in input().split(' ')]
total_0 = n // 2
total_1 = n - total_0
fixed_0 = len([p for p in ps if p == 0])
fixed_1 = len([p for p in ps if p == 1])
free_0 = total_0 - fixed_0
free_1 = total_1 - fixed_1

def mismatch(a, b):
	if a == -1:
		return 0
	if b == -1:
		assert False
	if a == b:
		return 0
	return 1

@functools.lru_cache(maxsize=None)
def solution(free_0, free_1, last, start_idx):
	assert free_0 >= 0
	assert free_1 >= 0
	assert start_idx <= n
	if start_idx == n:
		return 0
	head = ps[start_idx]
	if head != -1:
		return mismatch(last, head) + solution(free_0, free_1, head, start_idx + 1)
	assert head == -1
	if free_0 == 0:
		return mismatch(last, 1) + solution(free_0, free_1 - 1, 1, start_idx + 1)
	if free_1 == 0:
		return mismatch(last, 0) + solution(free_0 - 1, free_1, 0, start_idx + 1)
	return min(mismatch(last, 1) + solution(free_0, free_1 - 1, 1, start_idx + 1), mismatch(last, 0) + solution(free_0 - 1, free_1, 0, start_idx + 1))
	assert False
print(solution(free_0, free_1, -1, 0))


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def output(*args):
	sys.stdout.buffer.write(('\n'.join(map(str, args)) + '\n').encode('utf-8'))

def main():
	n = int(input())
	a = list(map(int, input().split()))
	odd_rem = len([i for i in range(1, n + 1, 2) if i not in a])
	zero_cnt = a.count(0)
	dp = [[[10 ** 6] * 2 for _ in range(odd_rem + 1)] for _ in range(n)]
	if a[0] == 0:
		if zero_cnt > odd_rem:
			dp[0][odd_rem][0] = 0
		if odd_rem > 0:
			dp[0][odd_rem - 1][1] = 0
		zero_cnt -= 1
	else:
		dp[0][odd_rem][a[0] & 1] = 0
	for i in range(1, n):
		is_zero = a[i] == 0
		parity = a[i] & 1
		for j in range(min(odd_rem, zero_cnt) + 1):
			for k in range(2):
				if not is_zero:
					dp[i][j][parity] = min(dp[i][j][parity], dp[i - 1][j][k] + (1 if parity != k else 0))
				else:
					if zero_cnt > j:
						dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][k] + (1 if k == 1 else 0))
					if j > 0:
						dp[i][j - 1][1] = min(dp[i][j - 1][1], dp[i - 1][j][k] + (1 if k == 0 else 0))
		if is_zero:
			zero_cnt -= 1
	print(min(dp[-1][0]))
main()


def calculate(ar, num):
	s = 0
	for x in range(len(ar)):
		if num >= ar[x][0]:
			num -= ar[x][0]
		else:
			s += 1 if ar[x][1] else 2
	return s

def calculate1(ar, num):
	s = calculate(ar, num)
	ar1 = []
	for x in range(len(ar)):
		if ar[x][1]:
			ar1.append(x)
	if len(ar1) >= 1:
		tmp = ar[ar1[0]]
		ar = ar[:ar1[0]] + ar[ar1[0] + 1:]
		s = min(s, calculate(ar, num) + 1)
		ar = ar[:ar1[0]] + [tmp] + ar[ar1[0]:]
	if len(ar1) == 2:
		ar = ar[:ar1[1]] + ar[ar1[1] + 1:]
		s = min(s, calculate(ar, num) + 1)
		ar = ar[:ar1[0]] + ar[ar1[0] + 1:]
		s = min(s, calculate(ar, num) + 2)
	return s
n = int(input())
p = list(map(int, input().split(' ')))
ar = [False] * (n + 1)
for x in p:
	if x != 0:
		ar[x] = True
if ar == [False] * (n + 1):
	if n == 1:
		print(0)
	else:
		print(1)
else:
	ones = 0
	zeros = 0
	for x in range(1, n + 1):
		if not ar[x]:
			if x % 2 == 0:
				zeros += 1
			else:
				ones += 1
	c = 0
	for x in range(1, n):
		if p[x] != 0 and p[x - 1] != 0 and (p[x] % 2 != p[x - 1] % 2):
			c += 1
	s = 0
	for x in range(n):
		if p[x] != 0:
			s = x
			break
	c1 = 0
	s1 = -1
	zerosp = []
	onesp = []
	c1 = 0
	for x in range(s + 1, n):
		if p[x] == 0:
			if s1 == -1:
				s1 = x
			c1 += 1
		elif c1 != 0:
			if p[s1 - 1] % 2 != p[x] % 2:
				c += 1
			elif p[s1 - 1] % 2 == 0:
				zerosp.append((c1, False))
			else:
				onesp.append((c1, False))
			s1 = -1
			c1 = 0
	if n >= 2:
		if p[0] == 0:
			if p[s] % 2 == 0:
				zerosp.append((s, True))
			else:
				onesp.append((s, True))
		if p[-1] == 0:
			c1 = 0
			s2 = 0
			for x in range(n - 2, -1, -1):
				c1 += 1
				if p[x] != 0:
					s2 = x
					break
			if p[s2] % 2 == 0:
				zerosp.append((c1, True))
			else:
				onesp.append((c1, True))
	c1 = 0
	zerosp = sorted(zerosp, key=lambda x: x[0])
	onesp = sorted(onesp, key=lambda x: x[0])
	print(c + calculate1(zerosp, zeros) + calculate1(onesp, ones))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math
n = int(input())
vals = list(map(int, input().split()))
complexity = 0
for s in range(n):
	if vals[s] == 0:
		vals[s] = 'x'
odds = math.ceil(n / 2)
evens = n // 2
for s in range(n):
	if vals[s] != 'x':
		if vals[s] % 2 == 0:
			evens -= 1
		else:
			odds -= 1
for s in range(1, n):
	if vals[s] != 'x':
		if vals[s - 1] != 'x':
			if vals[s - 1] % 2 != vals[s] % 2:
				complexity += 1
odd = []
sodd = []
even = []
seven = []
oddeven = []
chain = 0
start = (0, -1)
end = (0, 0)
for s in range(n):
	if vals[s] == 'x':
		chain += 1
	else:
		parity = vals[s] % 2
		end = (parity, s)
		if chain > 0:
			if start == (0, -1):
				if parity == 0:
					seven.append(chain)
				else:
					sodd.append(chain)
			elif start[0] == 0 and end[0] == 0:
				even.append(chain)
			elif start[0] == 1 and end[0] == 1:
				odd.append(chain)
			else:
				oddeven.append(chain)
		chain = 0
		start = (parity, s)
if vals[n - 1] == 'x':
	if chain > 0:
		if start == (0, 0):
			if n == 1:
				odd.append(chain)
			else:
				oddeven.append(chain)
		elif start[0] == 0:
			seven.append(chain)
		elif start[0] == 1:
			sodd.append(chain)
		else:
			oddeven.append(chain)
	chain = 0
odd.sort()
odd.reverse()
even.sort()
even.reverse()
oddeven.sort()
oddeven.reverse()
seven.sort()
seven.reverse()
sodd.sort()
sodd.reverse()
while odds > 0 and (len(odd) > 0 or len(sodd) > 0):
	if len(odd) > 0 and len(sodd) > 0:
		if len(sodd) == 2:
			if sum(sodd) < odd[-1]:
				odds -= sodd[-1]
				if odds >= 0:
					sodd.pop()
					odds -= sodd[-1]
					if odds >= 0:
						sodd.pop()
			elif odds >= odd[-1]:
				odds -= odd[-1]
				odd.pop()
			else:
				odds -= sodd[-1]
				if odds >= 0:
					sodd.pop()
		elif len(sodd) == 1:
			if odds >= odd[-1]:
				odds -= odd[-1]
				if odds >= 0:
					odd.pop()
			else:
				odds -= sodd[-1]
				if odds >= 0:
					sodd.pop()
	elif len(odd) > 0:
		odds -= odd[-1]
		if odds >= 0:
			odd.pop()
	else:
		odds -= sodd[-1]
		if odds >= 0:
			sodd.pop()
while evens > 0 and (len(even) > 0 or len(seven) > 0):
	if len(even) > 0 and len(seven) > 0:
		if len(seven) == 2:
			if sum(seven) < even[-1]:
				evens -= seven[-1]
				if evens >= 0:
					seven.pop()
					evens -= seven[-1]
					if evens >= 0:
						seven.pop()
			elif evens >= even[-1]:
				evens -= even[-1]
				even.pop()
			else:
				evens -= seven[-1]
				if evens >= 0:
					seven.pop()
		elif len(seven) == 1:
			if evens >= even[-1]:
				evens -= even[-1]
				if evens >= 0:
					even.pop()
			else:
				evens -= seven[-1]
				if evens >= 0:
					seven.pop()
	elif len(even) > 0:
		evens -= even[-1]
		if evens >= 0:
			even.pop()
	else:
		evens -= seven[-1]
		if evens >= 0:
			seven.pop()
complexity += len(odd) * 2 + len(even) * 2 + len(sodd) + len(seven) + len(oddeven)
if n == 1:
	print(0)
else:
	print(complexity)


debug = 0

def solve(n, a, war):
	mis = set(range(1, n + 1)).difference(a)
	typ = [0, 0, 0]
	typs = [[], [], []]
	i = 0
	juz = 0
	while i < n:
		if a[i] == 0:
			j = i
			while j < n and a[j] == 0:
				j += 1
			if i == 0 and j == n:
				return 0 if n == 1 else 1
			if i == 0:
				target = a[j] % 2
				if war[0]:
					target = 2
			elif j == n:
				target = a[i - 1] % 2
				if war[1]:
					target = 2
			elif a[i - 1] % 2 != a[j] % 2:
				target = 2
			else:
				target = a[i - 1] % 2
			typ[target] += 1
			typs[target].append(j - i)
			i = j
		else:
			if i > 0 and a[i - 1] != 0 and (a[i - 1] % 2 != a[i] % 2):
				juz += 1
			i += 1
	if debug:
		print(typ, typs)
	m0 = sum((1 for mm in mis if mm % 2 == 0))
	m1 = len(mis) - m0
	if debug:
		print(m0, m1)
	typs[0].sort()
	i = 0
	while i < len(typs[0]) and m0 >= typs[0][i]:
		m0 -= typs[0][i]
		i += 1
	remsol0 = len(typs[0]) - i
	typs[1].sort()
	i = 0
	while i < len(typs[1]) and m1 >= typs[1][i]:
		m1 -= typs[1][i]
		i += 1
	remsol1 = len(typs[1]) - i
	if debug:
		print(typ[2], remsol0, remsol1, juz, typ[2] + 2 * (remsol0 + remsol1) + juz)
	return typ[2] + 2 * (remsol0 + remsol1) + juz

def go():
	n = int(input())
	a = list(map(int, input().split()))
	print(min((solve(n, a, war) for war in [(0, 0), (0, 1), (1, 0), (1, 1)])))
go()


n = int(input())
p = list(map(int, input().split()))
inf = 10 ** 12
dp = [[[inf, inf] for j in range(101)] for i in range(n)]
if p[0] != 0:
	if p[0] % 2 == 0:
		dp[0][1][0] = 0
	else:
		dp[0][0][1] = 0
else:
	dp[0][1][0] = 0
	dp[0][0][1] = 0
for i in range(1, n):
	for j in range(101):
		for k in range(2):
			if dp[i - 1][j][k] == inf:
				continue
			if p[i] != 0:
				if p[i] % 2 == 0:
					if k == 0:
						dp[i][j + 1][0] = min(dp[i - 1][j][k], dp[i][j + 1][0])
					else:
						dp[i][j + 1][0] = min(dp[i - 1][j][k] + 1, dp[i][j + 1][0])
				elif k == 0:
					dp[i][j][1] = min(dp[i - 1][j][k] + 1, dp[i][j][1])
				else:
					dp[i][j][1] = min(dp[i - 1][j][k], dp[i][j][1])
			else:
				if k == 0:
					dp[i][j + 1][0] = min(dp[i - 1][j][k], dp[i][j + 1][0])
				else:
					dp[i][j + 1][0] = min(dp[i - 1][j][k] + 1, dp[i][j + 1][0])
				if k == 0:
					dp[i][j][1] = min(dp[i - 1][j][k] + 1, dp[i][j][1])
				else:
					dp[i][j][1] = min(dp[i - 1][j][k], dp[i][j][1])
print(min(dp[-1][n // 2]))


import sys
import math, bisect, operator
(inf, mod) = (float('inf'), 10 ** 9 + 7)
sys.setrecursionlimit(10 ** 5)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
I = lambda : int(sys.stdin.readline())
neo = lambda : map(int, sys.stdin.readline().split())
Neo = lambda : list(map(int, sys.stdin.readline().split()))
n = I()
a = Neo()
dp = [[[1000, 1000] for i in range(n + 1)] for j in range(n + 1)]
dp[0][0][0] = dp[0][0][1] = 0
for i in range(1, n + 1):
	k = a[i - 1]
	for j in range(i + 1):
		if k & 1 or k == 0:
			dp[i][j][1] = min(dp[i - 1][j][0] + 1, dp[i - 1][j][1])
		if k & 1 == 0:
			dp[i][j][0] = min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1] + 1)
print(min(dp[n][n >> 1]))


INF = 9999999999999999999999
n = int(input())
a = list(map(int, input().split()))
e = 0
o = 0
pref = [0 for i in range(n)]
for i in range(n):
	pref[i] = pref[i - 1]
	if a[i] == 0:
		pref[i] += 1
		continue
	if a[i] % 2 == 0:
		e += 1
	else:
		o += 1
ie = n // 2
io = ie
if n % 2 == 1:
	io += 1
e = ie - e
o = io - o
dp = [[[[INF for i in range(o + 1)] for j in range(e + 1)] for k in range(n)] for l in range(2)]
for i in range(n):
	jCap = min([pref[i], e])
	for j in range(jCap + 1):
		k = pref[i] - j
		if k <= o:
			if a[i] != 0:
				if i == 0:
					if a[0] % 2 == 0:
						dp[0][i][j][k] = 0
					else:
						dp[1][i][j][k] = 0
				elif a[i] % 2 == 0:
					dp[0][i][j][k] = min([dp[0][i - 1][j][k], 1 + dp[1][i - 1][j][k]])
				else:
					dp[1][i][j][k] = min([dp[1][i - 1][j][k], 1 + dp[0][i - 1][j][k]])
			elif i == 0:
				if j == 1:
					dp[0][i][j][k] = 0
				else:
					dp[1][i][j][k] = 0
			else:
				if j > 0:
					dp[0][i][j][k] = 1 + dp[1][i - 1][j - 1][k]
					dp[0][i][j][k] = min([dp[0][i][j][k], dp[0][i - 1][j - 1][k]])
				if k > 0:
					dp[1][i][j][k] = 1 + dp[0][i - 1][j][k - 1]
					dp[1][i][j][k] = min([dp[1][i][j][k], dp[1][i - 1][j][k - 1]])
print(min([dp[0][n - 1][e][o], dp[1][n - 1][e][o]]))


n = int(input())
b = list(map(int, input().split()))
j = 1
odd = 0
even = 0
while j <= n:
	if j % 2 == 0 and j not in b:
		even += 1
	elif j % 2 != 0 and j not in b:
		odd += 1
	j += 1
dp = []
for k in range(n):
	a = []
	for i in range(odd + 1):
		c = []
		for j in range(even + 1):
			r = []
			for q in range(2):
				r.append(float('inf'))
			c.append(r)
		a.append(c)
	dp.append(a)
res = 10 ** 7
if b[0] != 0:
	if b[0] % 2 == 0:
		dp[0][0][0][1] = 0
	else:
		dp[0][0][0][0] = 0
else:
	if even > 0:
		dp[0][0][1][1] = 0
	if odd > 0:
		dp[0][1][0][0] = 0
k = 1
while k < n:
	if b[k] != 0 and b[k - 1] != 0:
		if b[k] % 2 == 0 and b[k - 1] % 2 != 0:
			for i in range(odd + 1):
				for j in range(even + 1):
					dp[k][i][j][1] = min(dp[k][i][j][1], dp[k - 1][i][j][0] + 1)
		elif b[k] % 2 != 0 and b[k - 1] % 2 == 0:
			for i in range(odd + 1):
				for j in range(even + 1):
					dp[k][i][j][0] = min(dp[k][i][j][0], dp[k - 1][i][j][1] + 1)
		elif b[k] % 2 == 0 and b[k - 1] % 2 == 0:
			for i in range(odd + 1):
				for j in range(even + 1):
					dp[k][i][j][1] = min(dp[k][i][j][1], dp[k - 1][i][j][1])
		else:
			for i in range(odd + 1):
				for j in range(even + 1):
					dp[k][i][j][0] = min(dp[k][i][j][0], dp[k - 1][i][j][0])
	elif b[k] != 0 and b[k - 1] == 0:
		if b[k] % 2 == 0:
			for i in range(odd + 1):
				for j in range(even + 1):
					dp[k][i][j][1] = min(dp[k][i][j][1], dp[k - 1][i][j][0] + 1, dp[k - 1][i][j][1])
		else:
			for i in range(odd + 1):
				for j in range(even + 1):
					dp[k][i][j][0] = min(dp[k][i][j][0], dp[k - 1][i][j][1] + 1, dp[k - 1][i][j][0])
	elif b[k] == 0 and b[k - 1] != 0:
		if b[k - 1] % 2 == 0:
			for i in range(odd + 1):
				for j in range(even + 1):
					if i != 0 and j != 0:
						dp[k][i][j][0] = min(dp[k][i][j][0], dp[k - 1][i - 1][j][1] + 1)
						dp[k][i][j][1] = min(dp[k][i][j][1], dp[k - 1][i][j - 1][1])
					elif i != 0:
						dp[k][i][j][0] = min(dp[k][i][j][0], dp[k - 1][i - 1][j][1] + 1)
					elif j != 0:
						dp[k][i][j][1] = min(dp[k][i][j][1], dp[k - 1][i][j - 1][1])
		else:
			for i in range(odd + 1):
				for j in range(even + 1):
					if i != 0 and j != 0:
						dp[k][i][j][0] = min(dp[k][i][j][0], dp[k - 1][i - 1][j][0])
						dp[k][i][j][1] = min(dp[k][i][j][1], dp[k - 1][i][j - 1][0] + 1)
					elif i != 0:
						dp[k][i][j][0] = min(dp[k][i][j][0], dp[k - 1][i - 1][j][0])
					elif j != 0:
						dp[k][i][j][1] = min(dp[k][i][j][1], dp[k - 1][i][j - 1][0] + 1)
	else:
		for i in range(odd + 1):
			for j in range(even + 1):
				if i != 0 and j != 0:
					dp[k][i][j][0] = min(dp[k][i][j][0], dp[k - 1][i - 1][j][0], dp[k - 1][i - 1][j][1] + 1)
					dp[k][i][j][1] = min(dp[k][i][j][1], dp[k - 1][i][j - 1][1], dp[k - 1][i][j - 1][0] + 1)
				elif i != 0:
					dp[k][i][j][0] = min(dp[k][i][j][0], dp[k - 1][i - 1][j][0], dp[k - 1][i - 1][j][1] + 1)
				elif j != 0:
					dp[k][i][j][1] = min(dp[k][i][j][1], dp[k - 1][i][j - 1][1], dp[k - 1][i][j - 1][0] + 1)
	k += 1
print(min(dp[n - 1][odd][even]))


n = int(input())
p = input().split()
allnos = range(1, n + 1)
thenos = []
givnos = []
extra = []
comp = 0
no = None
gap = 0
for i in range(len(p)):
	if int(p[i]) != 0:
		givnos.append(int(p[i]))
		if no == None and gap > 0:
			extra.append([int(p[i]), int(p[i]), gap])
		elif gap > 0:
			thenos.append([no, int(p[i]), gap])
		elif no is not None and int(p[i]) % 2 != no % 2:
			comp += 1
		no = int(p[i])
		gap = 0
	else:
		gap += 1
if gap > 0:
	if no != None:
		extra.append([no, no, gap])
	else:
		if gap == 1:
			print('0')
		else:
			print('1')
		exit()
remnos = [item for item in allnos if item not in givnos]
pos = 0
neg = 0
for i in range(len(remnos)):
	if remnos[i] % 2 == 0:
		pos += 1
	else:
		neg += 1
thenos.sort(key=lambda x: x[2])
for ano in thenos:
	if ano[0] % 2 == ano[1] % 2:
		if ano[0] % 2 == 0:
			if ano[2] <= pos:
				pos -= ano[2]
			else:
				comp += 2
		elif ano[2] <= neg:
			neg -= ano[2]
		else:
			comp += 2
	else:
		comp += 1
for e in extra:
	if e[0] % 2 == 0:
		if e[2] > pos:
			comp += 1
		else:
			pos -= e[2]
	elif e[2] > neg:
		comp += 1
	else:
		neg -= e[2]
print(comp)


import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	a = list(map(int, input().split()))
	z = a.count(0)
	if n == 1:
		print(0)
	elif z == n:
		print(1)
	else:
		b = set(range(1, n + 1))
		for i in a:
			b.discard(i)
		(o, e) = (0, 0)
		for i in b:
			if i & 1:
				o += 1
			else:
				e += 1
		(i, z) = (0, [])
		while i < n:
			if a[i] == 0:
				j = i
				while j < n and a[j] == 0:
					j += 1
				z.append([i, j - 1])
				i = j
			i += 1
		z.sort(key=lambda x: x[1] - x[0] + 1 + (100000000 if x[0] == 0 or x[1] == n - 1 else 0))
		ans = 0
		for i in range(n - 1):
			if a[i] and a[i + 1] and (a[i] % 2 != a[i + 1] % 2):
				ans += 1
		for (l, r) in z:
			if l != 0 and r != n - 1:
				if a[l - 1] % 2 == a[r + 1] % 2:
					if a[l - 1] % 2:
						if o >= r - l + 1:
							o -= r - l + 1
						else:
							ans += 2
					elif e >= r - l + 1:
						e -= r - l + 1
					else:
						ans += 2
				else:
					ans += 1
			elif l == 0:
				if a[r + 1] % 2:
					if o >= r - l + 1:
						o -= r - l + 1
					else:
						ans += 1
				elif e >= r - l + 1:
					e -= r - l + 1
				else:
					ans += 1
			elif r == n - 1:
				if a[l - 1] % 2:
					if o >= r - l + 1:
						o -= r - l + 1
					else:
						ans += 1
				elif e >= r - l + 1:
					e -= r - l + 1
				else:
					ans += 1
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
N = int(input())
a = [int(x) for x in input().split(' ')]
if all((x == 0 for x in a)):
	print(0 if N == 1 else 1)
	sys.exit(0)
sz = [[], []]
(sl, sr, pl, pr) = (None, None, None, None)
cnt = [N // 2, (N + 1) // 2]
flips = 0
(pp, pi) = (None, -1)
for (i, x) in enumerate(a):
	if x != 0:
		if pp == None:
			sl = i - pi - 1
			pl = x % 2
		elif x % 2 != pp:
			flips += 1
		else:
			sz[x % 2].append(i - pi - 1)
		pp = x % 2
		pi = i
		cnt[x % 2] -= 1
sz[0].sort()
sz[1].sort()
sr = N - pi - 1
pr = pp
best_ans = 2 * N
for tl in [False, True]:
	for tr in [False, True]:
		f = cnt.copy()
		ans = flips
		if tl and f[pl] >= sl:
			f[pl] -= sl
		else:
			ans += 1
		if tr and f[pr] >= sr:
			f[pr] -= sr
		else:
			ans += 1
		for x in range(2):
			take = 0
			for y in sz[x]:
				if f[x] >= y:
					f[x] -= y
					take += 1
				else:
					break
			ans += 2 * (len(sz[x]) - take)
		best_ans = min(best_ans, ans)
print(best_ans)


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.readline
	N = int(input())
	P = list(map(int, input().split()))
	if N == 1:
		print(0)
		exit()
	if N == 2:
		print(1)
		exit()
	odd = (N + 1) // 2
	even = N // 2
	for p in P:
		if p:
			if p & 1:
				odd -= 1
			else:
				even -= 1
	inf = 10000
	dp0 = [[[inf] * N for _ in range(N)] for _ in range(N)]
	dp1 = [[[inf] * N for _ in range(N)] for _ in range(N)]
	if P[0]:
		if P[0] & 1:
			dp1[0][odd][even] = 0
		else:
			dp0[0][odd][even] = 0
	else:
		dp1[0][odd - 1][even] = 0
		dp0[0][odd][even - 1] = 0
	for i in range(1, N):
		for o in range(odd + 1):
			for e in range(even + 1):
				if P[i]:
					if P[i] & 1:
						dp1[i][o][e] = min(dp1[i - 1][o][e], dp0[i - 1][o][e] + 1)
					else:
						dp0[i][o][e] = min(dp1[i - 1][o][e] + 1, dp0[i - 1][o][e])
				else:
					if o:
						dp1[i][o - 1][e] = min(dp1[i - 1][o][e], dp0[i - 1][o][e] + 1)
					if e:
						dp0[i][o][e - 1] = min(dp1[i - 1][o][e] + 1, dp0[i - 1][o][e])
	print(min(dp0[-1][0][0], dp1[-1][0][0]))
main()


def abc(l, odd, even, i, x):
	try:
		return dp[i, odd, even, x]
	except:
		pass
	if i == len(l):
		return 0
	if l[i]:
		c = 0
		if x != l[i] % 2:
			c += 1
		return c + abc(l, odd, even, i + 1, l[i] % 2)
	ans = n
	if odd:
		c = 0
		if not x % 2:
			c += 1
		ans = min(ans, c + abc(l, odd - 1, even, i + 1, 1))
	if even:
		c = 0
		if x % 2:
			c += 1
		ans = min(ans, c + abc(l, odd, even - 1, i + 1, 0))
	dp[i, odd, even, x] = ans
	return ans
n = int(input())
l = list(map(int, input().split()))
dp = {}
odd = 0
even = 0
d = [0] * (n + 1)
for i in l:
	d[i] += 1
for i in range(1, n + 1):
	if i % 2 and (not d[i]):
		odd += 1
	if not i % 2 and (not d[i]):
		even += 1
if l[0]:
	print(abc(l, odd, even, 1, l[0] % 2))
else:
	ans = n
	if odd:
		ans = min(ans, abc(l, odd - 1, even, 1, 1))
	if even:
		ans = min(ans, abc(l, odd, even - 1, 1, 0))
	print(ans)


def inp(dtype=str, strip=True):
	s = input()
	res = [dtype(p) for p in s.split()]
	res = res[0] if len(res) == 1 and strip else res
	return res

def problem1():
	t = inp(int)
	for _ in range(t):
		n = inp(int)
		s = inp(str)
		i = 0
		while i < n and s[i] == 'P':
			i += 1
		res = 0
		while i < n:
			while i < n and s[i] == 'A':
				i += 1
			res1 = 0
			while i < n and s[i] == 'P':
				res1 += 1
				i += 1
			res = max(res, res1)
		print(res)

def problem2():
	(n, k) = inp(int)
	cards = []
	for _ in range(n):
		cards.append(inp(str))
	d = {c: i for (i, c) in enumerate(cards)}
	res = 0
	c3 = ['?'] * k
	for (i, c1) in enumerate(cards):
		for (j, c2) in enumerate(cards[i + 1:], i + 1):
			for ii in range(k):
				(l1, l2) = (c1[ii], c2[ii])
				if l1 == l2:
					c3[ii] = l1
				elif l1 == 'S' and l2 == 'E':
					c3[ii] = 'T'
				elif l1 == 'S':
					c3[ii] = 'E'
				elif l1 == 'E' and l2 == 'S':
					c3[ii] = 'T'
				elif l1 == 'E':
					c3[ii] = 'S'
				elif l2 == 'E':
					c3[ii] = 'S'
				else:
					c3[ii] = 'E'
			q = ''.join(c3)
			pos = d.get(q, -1)
			if pos >= 0 and pos > i and (pos > j):
				res += 1
	print(res)

def problem3():
	n = inp(int)
	p = inp(int, strip=False)
	avail = set(range(n + 1)).difference(p)
	nodd = sum([el % 2 == 1 for el in avail])
	neven = sum([el % 2 == 0 for el in avail])
	inf = 1000
	mat = [[[inf for _ in range(2)] for _ in range(nodd + 1)] for _ in range(n + 1)]
	mat[0][0][0] = mat[0][0][1] = 0
	used = 0
	for i in range(1, n + 1):
		pos = i - 1
		x = p[pos] % 2
		missing = p[pos] == 0
		if not missing:
			for usedodd in range(nodd + 1):
				mat[i][usedodd][x] = min(mat[i - 1][usedodd][0] + x, mat[i - 1][usedodd][1] + (1 - x))
		else:
			for usedodd in range(1, nodd + 1):
				mat[i][usedodd][1] = min(mat[i - 1][usedodd - 1][0] + 1, mat[i - 1][usedodd - 1][1])
			for usedodd in range(0, nodd + 1):
				mat[i][usedodd][0] = min(mat[i - 1][usedodd][0], mat[i - 1][usedodd][1] + 1)
		if missing:
			used += 1
	print(min(mat[n][nodd][0], mat[n][nodd][1]))

def problem4():
	pass

def problem5():
	pass
problem3()


import sys
input = lambda : sys.stdin.readline()
n = int(input())
if n == 1:
	print(0)
	exit(0)
a = list(map(int, input().split()))
t = -1
(o, e) = (0, 0)
for i in a:
	if i != 0:
		e += (i + 1) % 2
		o += i % 2
ans = 0
for j in range(n - 1):
	if a[j] != 0 and a[j + 1] != 0:
		ans += int(a[j] % 2 != a[j + 1] % 2)
e = n // 2 - e
o = n // 2 + n % 2 - o
l = -1
f = False
z = [[], [], [], [], []]
for i in range(n):
	if a[i] != 0:
		if f:
			f = False
			if l == -1:
				if a[i] % 2 == 0:
					z[0].append(i)
				else:
					z[1].append(i)
			elif a[i] % 2 == t:
				if t == 0:
					z[3].append(i - l - 1)
				else:
					z[4].append(i - l - 1)
			else:
				z[2].append(i - l - 1)
		l = i
		t = a[i] % 2
	else:
		f = True
if a[-1] == 0:
	if l == -1:
		print(1)
		exit(0)
	elif t == 0:
		z[0].append(n - l - 1)
	else:
		z[1].append(n - l - 1)
z[1].sort()
z[0].sort()
z[3].sort()
z[4].sort()
ans += len(z[2])
for i in range(len(z[3])):
	if z[3][i] <= e:
		e -= z[3][i]
	else:
		ans += (len(z[3]) - i) * 2
		break
for i in range(len(z[4])):
	if z[4][i] <= o:
		o -= z[4][i]
	else:
		ans += (len(z[4]) - i) * 2
		break
for i in range(len(z[0])):
	if z[0][i] <= e:
		e -= z[0][i]
	else:
		ans += len(z[0]) - i
		break
for i in range(len(z[1])):
	if z[1][i] <= o:
		o -= z[1][i]
	else:
		ans += len(z[1]) - i
		break
print(ans)


def parity(p):
	if p == 0:
		return 0
	return 1 if A[p] != A[p - 1] else 0

def sol(p, pa, ip):
	if pa < 0 or ip < 0:
		return 1000000
	if p == n:
		return 0
	if p > 0 and DP[p][ip][pa][A[p - 1]] != -1:
		return DP[p][ip][pa][A[p - 1]]
	if A[p] == -1:
		A[p] = 1
		r1 = sol(p + 1, pa, ip - 1) + parity(p)
		A[p] = 0
		r2 = sol(p + 1, pa - 1, ip) + parity(p)
		A[p] = -1
		if p > 0:
			DP[p][ip][pa][A[p - 1]] = min(r1, r2)
		return min(r1, r2)
	else:
		if p > 0:
			DP[p][ip][pa][A[p - 1]] = sol(p + 1, pa, ip) + parity(p)
		return sol(p + 1, pa, ip) + parity(p)
n = int(input())
A = [*map(int, input().split())]
if n == 1:
	print(0)
	exit(0)
par = n // 2
inp = n // 2 + n % 2
DP = [[[[-1, -1] for _ in range(par + 1)] for _ in range(inp + 1)] for _ in range(n + 1)]
for i in range(n):
	if A[i] == 0:
		A[i] = -1
	elif A[i] % 2 == 0:
		par -= 1
		A[i] = 0
	else:
		inp -= 1
		A[i] = 1
print(sol(0, par, inp))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

def main():
	n = int(input())
	l = [int(s) for s in input().split()]
	(e, o) = (n // 2, n - n // 2)
	for i in range(n):
		if l[i] != 0:
			if l[i] % 2 == 0:
				e -= 1
			else:
				o -= 1
	dp = [[[[-1, -1] for i in range(o + 1)] for j in range(e + 1)] for k in range(n + 1)]

	def solve(i, e, o, p):
		if dp[i][e][o][p] != -1:
			return dp[i][e][o][p]
		if i == 0:
			if l[i] != 0:
				if p == l[i] % 2:
					dp[i][e][o][p] = 0
					return 0
				else:
					dp[i][e][o][p] = 1000
					return 1000
			elif e == 0 and o == 0:
				dp[i][e][o][p] = 1000
				return 1000
			elif e == 0:
				if p == 0:
					dp[i][e][o][p] = 1000
					return 1000
				else:
					dp[i][e][o][p] = 0
					return 0
			elif o == 0:
				if p == 1:
					dp[i][e][o][p] = 1000
					return 1000
				else:
					dp[i][e][o][p] = 0
					return 0
			else:
				dp[i][e][o][p] = 0
				return 0
		if l[i] == 0:
			if p == 0:
				if e == 0:
					dp[i][e][o][p] = 1000
					return 1000
				w1 = solve(i - 1, e - 1, o, 1)
				w2 = solve(i - 1, e - 1, o, 0)
				if w1 + 1 < w2:
					dp[i][e][o][p] = w1 + 1
					return w1 + 1
				else:
					dp[i][e][o][p] = w2
					return w2
			else:
				if o == 0:
					dp[i][e][o][p] = 1000
					return 1000
				w1 = solve(i - 1, e, o - 1, 0)
				w2 = solve(i - 1, e, o - 1, 1)
				if w1 + 1 < w2:
					dp[i][e][o][p] = w1 + 1
					return w1 + 1
				else:
					dp[i][e][o][p] = w2
					return w2
		elif p != l[i] % 2:
			dp[i][e][o][p] = 1000
			return 1000
		elif p == 0:
			w1 = solve(i - 1, e, o, 1)
			w2 = solve(i - 1, e, o, 0)
			if w1 + 1 < w2:
				dp[i][e][o][p] = w1 + 1
				return w1 + 1
			else:
				dp[i][e][o][p] = w2
				return w2
		else:
			w1 = solve(i - 1, e, o, 0)
			w2 = solve(i - 1, e, o, 1)
			if w1 + 1 < w2:
				dp[i][e][o][p] = w1 + 1
				return w1 + 1
			else:
				dp[i][e][o][p] = w2
				return w2
	ans = min(solve(n - 1, e, o, 0), solve(n - 1, e, o, 1))
	print(ans)
main()


def arr_inp():
	return [int(x) for x in stdin.readline().split()]

def dp(i, odd, even, pre):
	if i >= n:
		return 0
	ret = mem[i, odd, even, pre]
	if ret != -1:
		return ret
	ret = float('inf')
	if a[i] > 0:
		if pre == 0:
			ret = min(ret, dp(i + 1, odd, even, a[i]))
		elif pre & 1 == 0 and a[i] & 1 or (pre & 1 and a[i] & 1 == 0):
			ret = min(ret, 1 + dp(i + 1, odd, even, a[i]))
		else:
			ret = min(ret, dp(i + 1, odd, even, a[i]))
	elif pre == 0:
		if odd:
			ret = min(ret, dp(i + 1, odd - 1, even, 1))
		if even:
			ret = min(ret, dp(i + 1, odd, even - 1, 2))
	elif pre & 1:
		if odd:
			ret = min(ret, dp(i + 1, odd - 1, even, 1))
		if even:
			ret = min(ret, 1 + dp(i + 1, odd, even - 1, 2))
	else:
		if even:
			ret = min(ret, dp(i + 1, odd, even - 1, 2))
		if odd:
			ret = min(ret, 1 + dp(i + 1, odd - 1, even, 1))
	mem[i, odd, even, pre] = ret
	return ret
from sys import stdin
from collections import defaultdict, Counter
(n, a, mem, o, e) = (int(input()), arr_inp(), defaultdict(lambda : -1), 0, 0)
c = defaultdict(int, Counter(a))
for i in range(1, n + 1):
	if c[i] == 0:
		if i & 1:
			o += 1
		else:
			e += 1
print(dp(0, o, e, 0))


n = int(input())
girl = list(map(int, input().split()))
odd = 0
even = 0
for g in girl:
	if g != 0:
		if g % 2 != 0:
			odd += 1
		else:
			even += 1
left_odd = (n + 1) // 2 - odd
left_even = n // 2 - even
series = []
left = 0
right = n - 1
while girl[left] == 0:
	left += 1
	if left == n:
		break
while girl[right] == 0:
	right -= 1
	if right == -1:
		break
if left > right:
	print(1 if n > 1 else 0)
	exit()
cur = None
ans = 0
for i in range(left, right + 1):
	if girl[i] != 0:
		if i < n - 1 and girl[i + 1] != 0 and (girl[i + 1] % 2 != girl[i] % 2):
			ans += 1
		if cur is not None:
			cur[1] = girl[i] % 2
			series.append(cur)
			cur = None
	elif cur is None:
		cur = [0, 0, 1]
		if i > 0:
			cur[0] = girl[i - 1] % 2
	else:
		cur[2] += 1
series.sort(key=lambda tup: tup[2])
for i in range(len(series)):
	s = series[i]
	if s[0] != s[1]:
		ans += 1
	elif s[0] % 2 != 0:
		if left_odd >= s[2]:
			left_odd -= s[2]
		else:
			ans += 2
	elif left_even >= s[2]:
		left_even -= s[2]
	else:
		ans += 2
if girl[left] % 2 == 0:
	if left_even < left:
		ans += 1
	else:
		left_even -= left
elif left_odd < left:
	ans += 1
else:
	left_odd -= left
if girl[right] % 2 == 0:
	if left_even < n - 1 - right:
		ans += 1
elif left_odd < n - 1 - right:
	ans += 1
print(ans)


n = int(input())
pis = [int(pi) for pi in input().split()]
(prev, current_gap, odd, even) = ('d', 0, 0, 0)
first_gap = ('e', 0)
(even_gaps, odd_gaps, any_gaps) = ([], [], [])
for pi in pis:
	if pi == 0:
		current_gap += 1
	elif pi % 2 == 0:
		even += 1
		if prev == 'o':
			any_gaps.append(current_gap)
		elif prev == 'e':
			even_gaps.append(current_gap)
		else:
			first_gap = ('e', current_gap)
		prev = 'e'
		current_gap = 0
	else:
		odd += 1
		if prev == 'e':
			any_gaps.append(current_gap)
		elif prev == 'o':
			odd_gaps.append(current_gap)
		else:
			first_gap = ('o', current_gap)
		prev = 'o'
		current_gap = 0
if prev == 'd':
	first_gap = ('o', current_gap)
ans = 0
odd_gaps.sort()
even_gaps.sort()
any_gaps.sort()
total_even = n // 2
total_odd = n - total_even
rem_odd = total_odd - odd
rem_even = total_even - even
for gap in odd_gaps:
	if rem_odd >= gap:
		rem_odd -= gap
	else:
		ans += 2
for gap in even_gaps:
	if rem_even >= gap:
		rem_even -= gap
	else:
		ans += 2
if current_gap > 0:
	if prev == 'o':
		if current_gap > rem_odd:
			ans += 1
		else:
			rem_odd -= current_gap
	elif prev == 'e':
		if current_gap > rem_even:
			ans += 1
		else:
			rem_even -= current_gap
if first_gap[0] == 'o' and first_gap[1] > rem_odd:
	ans += 1
if first_gap[0] == 'e' and first_gap[1] > rem_even:
	ans += 1
for gap in any_gaps:
	ans += 1
print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from types import GeneratorType

def bootstrap(func, stack=[]):

	def wrapped_function(*args, **kwargs):
		if stack:
			return func(*args, **kwargs)
		else:
			call = func(*args, **kwargs)
			while True:
				if type(call) is GeneratorType:
					stack.append(call)
					call = next(call)
				else:
					stack.pop()
					if not stack:
						break
					call = stack[-1].send(call)
			return call
	return wrapped_function

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()
from math import gcd
INF = 10 ** 18
MOD = 10 ** 9 + 7
n = int(ri())
a = Ri()
for i in range(len(a)):
	if a[i] != 0:
		a[i] = a[i] % 2
	else:
		a[i] = -1
ne = n // 2
no = ceil(n / 2)
dp = list4d(n, ne + 1, no + 1, 2, -1)

def solve(cur, ne, no, val):
	if ne < 0 or no < 0:
		return INF
	if cur < 0:
		return 0
	if a[cur] != -1 and a[cur] % 2 != val:
		return INF
	if dp[cur][ne][no][val] != -1:
		return dp[cur][ne][no][val]
	res1 = INF
	res2 = INF
	if val == 1:
		res1 = min(solve(cur - 1, ne, no - 1, 1), 1 + solve(cur - 1, ne, no - 1, 0))
	else:
		res2 = min(1 + solve(cur - 1, ne - 1, no, 1), solve(cur - 1, ne - 1, no, 0))
	dp[cur][ne][no][val] = min(res1, res2)
	return dp[cur][ne][no][val]
ans = min(solve(n - 1, ne, no, 0), solve(n - 1, ne, no, 1))
print(ans)


n = int(input())
cou = [n // 2, n // 2]
if n % 2 != 0:
	cou[1] += 1
a = [int(o) for o in input().split()]
for i in range(n):
	if a[i] == 0:
		a[i] = -1
	else:
		a[i] %= 2
		cou[a[i]] -= 1
curr = 0
ps = []
ans = 0
ns = []
fl = []
for i in range(1, n):
	if a[i] != -1:
		if a[i] != a[curr]:
			if a[curr] == -1:
				fl.append([i, a[i], curr - 1, i - 1])
			else:
				ns.append([i - curr - 1, a[i], curr, i - 1])
		else:
			ps.append([i - curr - 1, a[i], curr, i - 1])
		curr = i
if a[n - 1] == -1:
	fl.append([n - 1 - curr, a[curr], curr + 1, n])
ps.sort()
ns.sort()
fl.sort()
flag = 0
for i in ps:
	if flag == 1 or i[0] <= cou[i[1]]:
		for j in range(i[3], i[2], -1):
			if cou[i[1]] > 0:
				cou[i[1]] -= 1
				a[j] = i[1]
			else:
				cou[(i[1] + 1) % 2] -= 1
				a[j] = (i[1] + 1) % 2
	else:
		for k in fl:
			if k[3] == n:
				for j in range(k[2], k[3]):
					if cou[k[1]] > 0:
						cou[k[1]] -= 1
						a[j] = k[1]
					else:
						cou[(k[1] + 1) % 2] -= 1
						a[j] = (k[1] + 1) % 2
			else:
				for j in range(k[3], k[2], -1):
					if cou[k[1]] > 0:
						cou[k[1]] -= 1
						a[j] = k[1]
					else:
						cou[(k[1] + 1) % 2] -= 1
						a[j] = (k[1] + 1) % 2
		for j in range(i[3], i[2], -1):
			if cou[i[1]] > 0:
				cou[i[1]] -= 1
				a[j] = i[1]
			else:
				cou[(i[1] + 1) % 2] -= 1
				a[j] = (i[1] + 1) % 2
		flag = 1
if fl and flag == 0:
	if 1:
		for k in fl:
			if k[3] == n:
				for j in range(k[2], k[3]):
					if cou[k[1]] > 0:
						cou[k[1]] -= 1
						a[j] = k[1]
					else:
						cou[(k[1] + 1) % 2] -= 1
						a[j] = (k[1] + 1) % 2
			else:
				for j in range(k[3], k[2], -1):
					if cou[k[1]] > 0:
						cou[k[1]] -= 1
						a[j] = k[1]
					else:
						cou[(k[1] + 1) % 2] -= 1
						a[j] = (k[1] + 1) % 2
for i in ns:
	for j in range(i[3], i[2], -1):
		if cou[i[1]] > 0:
			cou[i[1]] -= 1
			a[j] = i[1]
		else:
			cou[(i[1] + 1) % 2] -= 1
			a[j] = (i[1] + 1) % 2
if a[0] == -1 and len(a) > 1:
	a[0] = a[1]
ans = 0
for i in range(1, n):
	if a[i] != a[i - 1]:
		ans += 1
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
DP0 = [[200] * (n + 1) for i in range(n + 1)]
DP1 = [[200] * (n + 1) for i in range(n + 1)]
DP0[0][0] = 0
DP1[0][0] = 0
for i in range(n):
	SUM = i + 1
	if A[i] != 0:
		if A[i] % 2 == 1:
			for j in range(1, SUM + 1):
				DP1[j][SUM - j] = min(DP0[j - 1][SUM - j] + 1, DP1[j - 1][SUM - j])
		else:
			for j in range(1, SUM + 1):
				DP0[SUM - j][j] = min(DP0[SUM - j][j - 1], DP1[SUM - j][j - 1] + 1)
	else:
		for j in range(1, SUM + 1):
			DP1[j][SUM - j] = min(DP0[j - 1][SUM - j] + 1, DP1[j - 1][SUM - j])
		for j in range(1, SUM + 1):
			DP0[SUM - j][j] = min(DP0[SUM - j][j - 1], DP1[SUM - j][j - 1] + 1)
ANS = min(DP0[n - n // 2][n // 2], DP1[n - n // 2][n // 2])
print(ANS)


from math import ceil, inf
n = int(input())
p = [int(x) for x in input().split()]
(o, e) = (0, 0)
for i in p:
	if i != 0:
		if i % 2:
			o += 1
		else:
			e += 1
o = ceil(n / 2)
dp = [[[inf, inf] for i in range(n + 1)] for j in range(n)]
if p[0] == 0:
	dp[0][0][0] = 0
	dp[0][1][1] = 0
else:
	dp[0][p[0] % 2][p[0] % 2] = 0
for i in range(1, n):
	if p[i] % 2 != 1:
		dp[i][0][0] = min(dp[i - 1][0][0], dp[i][0][0])
	else:
		dp[i][0][0] = inf
	for j in range(1, o + 1):
		if p[i] == 0:
			dp[i][j][1] = min(dp[i - 1][j - 1][0] + 1, dp[i - 1][j - 1][1], dp[i][j][1])
			dp[i][j][0] = min(dp[i - 1][j][0], dp[i - 1][j][1] + 1, dp[i][j][0])
		elif p[i] % 2 == 1:
			dp[i][j][1] = min(dp[i - 1][j - 1][0] + 1, dp[i - 1][j - 1][1], dp[i][j][1])
			dp[i][j][0] = inf
		else:
			dp[i][j][0] = min(dp[i - 1][j][0], dp[i - 1][j][1] + 1, dp[i][j][0])
			dp[i][j][1] = inf
print(min(dp[-1][o]))


import sys
import collections
from collections import Counter
import itertools
import math
import timeit

def sieve(n):
	if n < 2:
		return list()
	prime = [True for _ in range(n + 1)]
	p = 3
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 2
	r = [2]
	for p in range(3, n + 1, 2):
		if prime[p]:
			r.append(p)
	return r

def divs(n, start=1):
	divisors = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				divisors.append(i)
			else:
				divisors.extend([i, n // i])
	return divisors

def divn(n, primes):
	divs_number = 1
	for i in primes:
		if n == 1:
			return divs_number
		t = 1
		while n % i == 0:
			t += 1
			n //= i
		divs_number *= t

def flin(d, x, default=-1):
	left = right = -1
	for i in range(len(d)):
		if d[i] == x:
			if left == -1:
				left = i
			right = i
	if left == -1:
		return (default, default)
	else:
		return (left, right)

def ceil(n, k):
	return int(n // k + (n % k != 0))

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def prr(a, sep=' '):
	print(sep.join(map(str, a)))

def dd():
	return collections.defaultdict(int)

def ddl():
	return collections.defaultdict(list)
n = ii()
d = li()
if all((i == 0 for i in d)):
	print(1) if n > 1 else print(0)
	exit()
even = n // 2
odd = ceil(n, 2)
fpos = lpos = -1
for i in range(n):
	if d[i] != 0:
		if fpos == -1:
			fpos = i
		lpos = i
		if d[i] % 2:
			odd -= 1
		else:
			even -= 1
odd_s = []
even_s = []
i = j = fpos
while i < n:
	if d[i] != 0:
		i += 1
		continue
	j = i
	while j < n and d[j] == 0:
		j += 1
	if j < n and d[i - 1] % 2 == d[j] % 2:
		if d[j] % 2:
			odd_s.append((j - i, i, j))
		else:
			even_s.append((j - i, i, j))
	i = j
odd_s.sort()
even_s.sort()
for p in odd_s:
	if odd < p[0]:
		break
	for i in range(p[1], p[2]):
		(d[i], odd) = (1, odd - 1)
for p in even_s:
	if even < p[0]:
		break
	for i in range(p[1], p[2]):
		(d[i], even) = (2, even - 1)
if d[fpos] % 2:
	if fpos <= odd:
		for i in range(fpos):
			(d[i], odd) = (1, odd - 1)
elif fpos <= even:
	for i in range(fpos):
		(d[i], even) = (2, even - 1)
if d[lpos] % 2:
	if n - lpos - 1 <= odd:
		for i in range(lpos + 1, n):
			(d[i], odd) = (1, odd - 1)
elif n - lpos - 1 <= even:
	for i in range(lpos + 1, n):
		(d[i], even) = (2, even - 1)
for i in range(n):
	if d[i] % 2:
		l = i - 1
		while l >= 0 and d[l] == 0 and (odd > 0):
			(d[l], odd, l) = (1, odd - 1, l - 1)
		r = i + 1
		while r < n and d[r] == 0 and (odd > 0):
			(d[r], odd, r) = (1, odd - 1, r + 1)
	elif d[i] != 0:
		l = i - 1
		while l >= 0 and d[l] == 0 and (even > 0):
			(d[l], even, l) = (2, even - 1, l - 1)
		r = i + 1
		while r < n and d[r] == 0 and (even > 0):
			(d[r], even, r) = (2, even - 1, r + 1)
f = 2 if even != 0 else 1
for i in range(n):
	if d[i] == 0:
		d[i] = f
res = 0
for i in range(n - 1):
	if d[i] % 2 != d[i + 1] % 2 and d[i] != 0 and (d[i + 1] != 0):
		res += 1
print(res)


from functools import lru_cache
n = int(input())
p = list(map(int, input().split()))
c = [i % 2 for i in p].count(1)
if n % 2 == 0:
	t = n // 2 - c
else:
	t = n // 2 - c + 1

@lru_cache(None)
def dfs(i, t, q):
	if t < 0 or t > n - i:
		return float('inf')
	elif i == n:
		return 0 if t == 0 else float('inf')
	if p[i] == 0:
		if q == 0:
			return min(dfs(i + 1, t, 0), dfs(i + 1, t - 1, 1) + 1)
		else:
			return min(dfs(i + 1, t - 1, 1), dfs(i + 1, t, 0) + 1)
	else:
		return abs(q - p[i] % 2) + dfs(i + 1, t, p[i] % 2)
if p[0] == 0:
	print(min(dfs(1, t - 1, 1), dfs(1, t, 0)))
else:
	print(dfs(1, t, p[0] % 2))


n = int(input())
a = [int(i) for i in input().split()]
odd = n // 2 + (n & 1)
even = n // 2
if sum(a) == 0:
	print(1) if n > 1 else print(0)
	exit(0)
for i in a:
	if i & 1 == 1:
		odd -= 1
	elif i & 1 == 0 and i != 0:
		even -= 1
ans = 0
s = [[], [], []]
for i in range(0, len(a) - 1):
	if a[i] & 1 != a[i + 1] & 1:
		if a[i] != 0 and a[i + 1] != 0:
			ans += 1
n1 = 0
n2 = 0
for i in range(len(a)):
	if a[i] != 0 and a[i] % 2 == 0:
		n1 = i
		break
	if a[i] != 0 and a[i] % 2 == 1:
		n2 = i
		break
i = 0
n11 = 0
n22 = 0
while i < len(a):
	if a[i] != 0:
		for j in range(i + 1, len(a)):
			if a[j] != 0:
				s[a[i] % 2 + a[j] % 2].append(j - i - 1)
				i = j
				break
		if j == len(a) - 1:
			if a[i] % 2 == 0:
				n11 = len(a) - i - 1
			else:
				n22 = len(a) - i - 1
			break
	else:
		i += 1
for i in s:
	i.sort()
for i in range(len(s[0])):
	if s[0][i] <= even:
		even -= s[0][i]
	else:
		ans += 2 * len(s[0][i:])
		break
if n1:
	if n1 > even:
		ans += 1
	else:
		even -= n1
if n11:
	if n11 > even:
		ans += 1
	else:
		even -= n11
for i in range(len(s[2])):
	if s[2][i] <= odd:
		odd -= s[2][i]
	else:
		ans += 2 * len(s[2][i:])
		break
if n2:
	if n2 > odd:
		ans += 1
	else:
		odd -= n2
if n22:
	if n22 > odd:
		ans += 1
	else:
		odd -= n22
for i in s[1]:
	if i != 0:
		ans += 1
print(ans)


from collections import deque
from random import shuffle, random
n = int(input())
lamps = list(map(int, input().split()))

def calc(n, lamps):
	counts = [0, 0]
	counts[0] = n // 2
	counts[1] = n // 2
	counts[1] += n % 2
	lines = []
	start_idx = None
	diff = 0
	for i in range(1, len(lamps)):
		if lamps[i] != 0 and lamps[i - 1] != 0 and (lamps[i] % 2 != lamps[i - 1] % 2):
			diff += 1
	for el in lamps:
		if el != 0:
			counts[el % 2] -= 1
	for (i, el) in enumerate(lamps):
		if el == 0:
			if start_idx is None:
				start_idx = i
		elif start_idx is not None:
			lines.append((i - start_idx, lamps[start_idx - 1] % 2 if start_idx > 0 else -1, lamps[i] % 2))
			start_idx = None
	if start_idx is not None:
		lines.append((len(lamps) - start_idx, lamps[start_idx - 1] % 2 if start_idx > 0 else -1, -1))
	lines.sort()
	penalty = [[[], []], [[], []]]
	for i in range(len(lines)):
		(length, a, b) = lines[i]
		if a != -1 and b != -1:
			if a == b:
				penalty[a][1].append(length)
				diff += 2
			else:
				diff += 1
		elif a == -1 and b == -1:
			diff += int(n > 1)
		else:
			res = a if a != -1 else b
			diff += 1
			penalty[res][0].append(length)
	for pos in range(2):
		pen = penalty[pos]
		x = 0
		y = 0
		while y < len(pen[1]) and pen[1][y] <= counts[pos]:
			if len(pen[0]) - x >= 2 and pen[0][x] + pen[0][x + 1] <= pen[1][y]:
				diff -= 2
				counts[pos] -= pen[0][x] + pen[0][x + 1]
				x += 2
			else:
				diff -= 2
				counts[pos] -= pen[1][y]
				y += 1
		while x < len(pen[0]) and pen[0][x] <= counts[pos]:
			diff -= 1
			counts[pos] -= pen[0][x]
			x += 1
	return diff
print(calc(n, lamps))


n = int(input())
ps = list(map(int, input().split()))
s = set(ps)
cnt = [0, 0]
for elem in range(1, n + 1):
	if not elem in s:
		cnt[elem % 2] += 1

def eq(a, b):
	if a == b:
		return 0
	return 1
m = {}

def solve(idx, even, odd, last):
	if idx == n:
		return 0
	key = (idx, even, odd, last)
	if key in m:
		return m[key]
	ans = 0
	if ps[idx] == 0:
		ev = 1000000000.0
		od = 1000000000.0
		if even > 0:
			ev = eq(last, 0)
			ev += solve(idx + 1, even - 1, odd, 0)
		if odd > 0:
			od = eq(last, 1)
			od += solve(idx + 1, even, odd - 1, 1)
		ans = min(ev, od)
	else:
		pa = ps[idx] % 2
		ans = eq(last, pa)
		ans += solve(idx + 1, even, odd, pa)
	m[key] = ans
	return ans
(even, odd) = cnt
print(min(solve(0, even, odd, 0), solve(0, even, odd, 1)))


import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
odd = 0
even = 0
if n % 2:
	odd = n // 2 + 1
	even = n // 2
else:
	odd = n // 2
	even = n // 2
jugad = [[[[100 for i in range(2)] for j in range(50 + 2)] for k in range(50 + 2)] for l in range(100 + 2)]
jugad[0][0][0][0] = 0
jugad[0][0][0][1] = 0
for i in range(1, n + 1):
	for j in range(odd + 1):
		for k in range(even + 1):
			if arr[i - 1] == 0:
				if k > 0:
					jugad[i][j][k][0] = min(jugad[i - 1][j][k - 1][0], jugad[i - 1][j][k - 1][1] + 1)
				if j > 0:
					jugad[i][j][k][1] = min(jugad[i - 1][j - 1][k][0] + 1, jugad[i - 1][j - 1][k][1])
			elif arr[i - 1] % 2:
				if j > 0:
					jugad[i][j][k][1] = min(jugad[i - 1][j - 1][k][0] + 1, jugad[i - 1][j - 1][k][1])
			elif k > 0:
				jugad[i][j][k][0] = min(jugad[i - 1][j][k - 1][0], jugad[i - 1][j][k - 1][1] + 1)
print(min(jugad[n][odd][even][0], jugad[n][odd][even][1]))


n = int(input())
a = list(map(int, input().split()))
z = []
if len(set(a)) == 1:
	if len(a) == 1:
		print(0)
	else:
		print(1)
	exit()
even = n // 2
odd = n - even
for i in a:
	if i:
		if i % 2:
			odd -= 1
		else:
			even -= 1
for i in a:
	if i == 0:
		if not z:
			z.append(1)
		elif z[-1] != 'o' and z[-1] != 'e':
			z[-1] += 1
		else:
			z.append(1)
	elif i % 2 == 0:
		z.append('e')
	else:
		z.append('o')
count = 0
(oddneeded, evenneeded) = ([], [])
(oddcorner, evencorner) = ([], [])
for i in range(len(z)):
	if z[i] == 'o' or z[i] == 'e':
		continue
	if i == 0:
		if z[i + 1] == 'o':
			oddcorner.append([z[i], i])
		else:
			evencorner.append([z[i], i])
	elif i == len(z) - 1:
		if z[i - 1] == 'o':
			oddcorner.append([z[i], i])
		else:
			evencorner.append([z[i], i])
	elif z[i - 1] == z[i + 1]:
		if z[i - 1] == 'o':
			if i != 0 and i != len(z) - 1:
				oddneeded.append([z[i], i])
		elif i != 0 and i != len(z) - 1:
			evenneeded.append([z[i], i])
	else:
		z[i] = 'e'
oddneeded.sort(reverse=True)
evenneeded.sort(reverse=True)
oddcorner.sort(reverse=True)
evencorner.sort(reverse=True)
while oddneeded:
	if oddneeded[-1][0] <= odd:
		x = oddneeded.pop()
		odd -= x[0]
		z[x[1]] = 'o'
	else:
		break
for i in oddneeded:
	z[i[1]] = 'e'
while oddcorner:
	if oddcorner[-1][0] <= odd:
		x = oddcorner.pop()
		odd -= x[0]
		z[x[1]] = 'o'
	else:
		break
for i in oddcorner:
	z[i[1]] = 'e'
while evenneeded:
	if evenneeded[-1][0] <= even:
		x = evenneeded.pop()
		even -= x[0]
		z[x[1]] = 'e'
	else:
		break
for i in evenneeded:
	z[i[1]] = 'o'
while evencorner:
	if evencorner[-1][0] <= even:
		x = evencorner.pop()
		even -= x[0]
		z[x[1]] = 'e'
	else:
		break
for i in evencorner:
	z[i[1]] = 'o'
for i in range(1, len(z)):
	if z[i] != z[i - 1]:
		count += 1
print(count)


import sys
n = int(input())
s = list(map(int, input().split()))
rec = [[], [], []]
dif = 0
b = 0
while b < n:
	if s[b] == 0:
		tag = b
		while s[tag] == 0:
			tag += 1
			if tag == n:
				break
		le = tag - b
		if b == 0 and tag == n:
			if n == 1:
				print(0)
			else:
				print(1)
			sys.exit()
		elif b == 0:
			rec[1].append((le, s[tag] % 2))
		elif tag == n:
			rec[2].append((le, s[b - 1] % 2))
		elif s[b - 1] % 2 == s[tag] % 2:
			rec[0].append((le, s[b - 1] % 2))
		else:
			dif += 1
		b = tag
	b += 1
(odd, eve) = (0, 0)
for (i, v) in enumerate(s):
	if v != 0:
		if i + 1 < n and s[i + 1] % 2 != s[i] % 2 and (s[i + 1] != 0):
			dif += 1
		if v % 2 == 0:
			eve += 1
		else:
			odd += 1
import math
(heve, hodd) = (n // 2 - eve, math.ceil(n / 2) - odd)
res = 0
for (i, v) in enumerate(rec):
	v.sort()
	for (l, p) in v:
		if p == 0:
			if l <= heve:
				heve -= l
			elif i == 1 or i == 2:
				res += 1
			else:
				res += 2
		elif l <= hodd:
			hodd -= l
		elif i == 1 or i == 2:
			res += 1
		else:
			res += 2
print(res + dif)


import sys
n = int(input())
if n == 1:
	print(0)
	sys.exit()
arr = list(map(int, input().split()))
arr = [i % 2 if i != 0 else -1 for i in arr]
skipped = sum([i == -1 for i in arr])
if skipped == n:
	print(1)
	sys.exit()
ans = 0
for i in range(n - 1):
	if arr[i] == 0 and arr[i + 1] == 1 or (arr[i] == 1 and arr[i + 1] == 0):
		ans += 1
if skipped == 0:
	print(ans)
	sys.exit()
even = n // 2 - sum([i == 0 for i in arr])
odd = skipped - even
if 0 not in arr:
	arr = [1] + arr + [1]
elif 1 not in arr:
	arr = [0] + arr + [0]
else:
	first = arr[min(arr.index(0), arr.index(1))]
	last = arr[n - 1 - min(arr[::-1].index(0), arr[::-1].index(1))]
	arr = [first] + arr + [last]
substrs = []
i = 0
while i != n + 2:
	if arr[i] != -1:
		i += 1
		continue
	(left, j) = (arr[i - 1], i - 1)
	while arr[i] == -1:
		i += 1
	right = arr[i]
	if left != right:
		ans += 1
	else:
		substrs.append((j == 0 or i == n + 1, i - j - 1, left))
substrs.sort()
for (l, i, j) in substrs:
	if j == 0:
		if even >= i:
			even -= i
		else:
			ans += 2 - l
	elif odd >= i:
		odd -= i
	else:
		ans += 2 - l
print(ans)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
from itertools import permutations
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
N = int(input())
A = [int(a) for a in input().split()]
M = A.count(0)
A2 = [a % 2 for a in A]
O = A2.count(1)
E = N - M - O
O = (N + 1) // 2 - O
E = N // 2 - E
C = [M]
for a in A:
	C.append(C[-1] - (a == 0))
X = [[999] * 102 for _ in range(N)]
Y = [[999] * 102 for _ in range(N)]
if A[0] % 2:
	X[0][O] = 0
elif A[0]:
	Y[0][O] = 0
else:
	if O:
		X[0][O - 1] = 0
	if E:
		Y[0][O] = 0
for i in range(1, N):
	for j in range(N + 1):
		if A[i] % 2:
			X[i][j] = min(X[i - 1][j], Y[i - 1][j] + 1)
		elif A[i]:
			Y[i][j] = min(X[i - 1][j] + 1, Y[i - 1][j])
		else:
			X[i][j] = min(X[i - 1][j + 1], Y[i - 1][j + 1] + 1)
			Y[i][j] = min(X[i - 1][j] + 1, Y[i - 1][j])
print(min(X[N - 1][0], Y[N - 1][0]))


n = int(input())
a = list(map(int, input().split()))
e = n // 2
o = n - e
ptf = [[[0, 0] for i in range(e + 2)] for j in range(o + 2)]
dt = {}
for i in range(n):
	if a[i] != 0:
		dt[i + 1] = a[i]
for i in range(o + 1):
	for j in range(e + 1):
		if i == 0:
			ptf[i][j][0] = 99999
		if j == 0:
			ptf[i][j][1] = 99999
		if i + j in dt:
			if dt[i + j] % 2 == 1:
				ptf[i][j][1] = 99999
			else:
				ptf[i][j][0] = 99999
ptf[0][0][0] = 0
ptf[0][0][1] = 0
for i in range(o + 1):
	for j in range(e + 1):
		if ptf[i][j + 1][1] < 9999:
			ptf[i][j + 1][1] = min(ptf[i][j][1], ptf[i][j][0] + 1)
		if ptf[i + 1][j][0] < 9999:
			ptf[i + 1][j][0] = min(ptf[i][j][0], ptf[i][j][1] + 1)
print(min(ptf[i][j][0], ptf[i][j][1]))