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 ≤ n ≤ 100) — the number of light bulbs on the garland.

The second line contains n integers p_1,\ p_2,\ …,\ p_n (0 ≤ p_i ≤ 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:
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)


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


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)


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


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)


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


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)


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


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


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)


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)


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())
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())
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] * (N + 2) for _ in range(N)]
Y = [[999] * (N + 2) 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())
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]))


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)


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


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


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)


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]
odd = ceil(N, 2)
even = N // 2
dp = list4d(N + 1, odd + 1, even + 1, 2, INF)
dp[0][0][0][0] = dp[0][0][0][1] = 0
for i in range(N):
	a = A[i]
	for j in range(odd + 1):
		for k in range(even + 1):
			for l in range(2):
				if (a == 1 or a == -1) and j + 1 <= odd:
					dp[i + 1][j + 1][k][1] = min(dp[i + 1][j + 1][k][1], dp[i][j][k][l] + (1 ^ l))
				if (a == 0 or a == -1) and k + 1 <= even:
					dp[i + 1][j][k + 1][0] = min(dp[i + 1][j][k + 1][0], dp[i][j][k][l] + (0 ^ l))
ans = min(dp[N][odd][even][0], dp[N][odd][even][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())
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]))


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


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


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


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


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


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


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


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)


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)


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


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)


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


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)


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


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


def gcd(a, b):
	return math.gcd(a, b)

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

def ncr(n, r):
	return math.comb(n, r)

def npr(n, r):
	return math.factorial(n) // math.factorial(n - r)

def decimal_to_binary(n):
	return bin(n).replace('0b', '')

def binary_to_decimal(s):
	return int(s, 2)
import sys, os.path
import math
from collections import defaultdict, deque
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
S = lambda : list(map(str, input1()))
mem1 = {}

def solve(i, prev, even, odd):
	if i >= len(p):
		return 0
	if (i, prev, even, odd) in mem1:
		return mem1[i, prev, even, odd]
	if p[i] == 0:
		if prev == 1:
			op1 = 10 ** 10
			op2 = 10 ** 10
			if even > 0:
				op1 = 1 + solve(i + 1, 0, even - 1, odd)
			if odd > 0:
				op2 = solve(i + 1, 1, even, odd - 1)
			mem1[i, prev, even, odd] = min(op1, op2)
			return mem1[i, prev, even, odd]
		else:
			op1 = 10 ** 10
			op2 = 10 ** 10
			if even > 0:
				op1 = solve(i + 1, 0, even - 1, odd)
			if odd > 0:
				op2 = 1 + solve(i + 1, 1, even, odd - 1)
			mem1[i, prev, even, odd] = min(op1, op2)
			return mem1[i, prev, even, odd]
	else:
		op1 = 10 ** 10
		op2 = 10 ** 10
		if p[i] % 2 == 0:
			if prev == 1:
				op1 = 1 + solve(i + 1, 0, even, odd)
			else:
				op1 = solve(i + 1, 0, even, odd)
		elif prev == 1:
			op1 = solve(i + 1, 1, even, odd)
		else:
			op1 = 1 + solve(i + 1, 1, even, odd)
		mem1[i, prev, even, odd] = min(op1, op2)
		return mem1[i, prev, even, odd]
(n,) = I()
p = I()
count = [0] * 102
for i in range(len(p)):
	count[p[i]] = 1
counte = 0
counto = 0
for i in range(1, n + 1):
	if count[i] == 0 and i % 2 == 0:
		counte += 1
	if count[i] == 0 and i % 2 != 0:
		counto += 1
if p[0] == 0:
	op1 = 10 ** 10
	op2 = 10 ** 10
	if counte > 0:
		op1 = solve(1, 0, counte - 1, counto)
	if counto > 0:
		op2 = solve(1, 1, counte, counto - 1)
	print(min(op1, op2))
elif p[0] % 2 == 0:
	print(solve(1, 0, counte, counto))
else:
	print(solve(1, 1, counte, counto))


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


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


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


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


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


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


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)


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)


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


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)


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)


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