Snuke stands on a number line. He has L ears, and he will walk along the line continuously under the following conditions:

* He never visits a point with coordinate less than 0, or a point with coordinate greater than L.
* He starts walking at a point with integer coordinate, and also finishes walking at a point with integer coordinate.
* He only changes direction at a point with integer coordinate.



Each time when Snuke passes a point with coordinate i-0.5, where i is an integer, he put a stone in his i-th ear.

After Snuke finishes walking, Ringo will repeat the following operations in some order so that, for each i, Snuke's i-th ear contains A_i stones:

* Put a stone in one of Snuke's ears.
* Remove a stone from one of Snuke's ears.



Find the minimum number of operations required when Ringo can freely decide how Snuke walks.

Constraints

* 1 \leq L \leq 2\times 10^5
* 0 \leq A_i \leq 10^9(1\leq i\leq L)
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


L
A_1
:
A_L


Output

Print the minimum number of operations required when Ringo can freely decide how Snuke walks.

Examples

Input

4
1
0
2
3


Output

1


Input

8
2
0
0
2
1
3
4
1


Output

3


Input

7
314159265
358979323
846264338
327950288
419716939
937510582
0


Output

1
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
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

"""
状態をそのままdpのインデックスとする。
https://drken1215.hatenablog.com/entry/2019/02/10/014800
"""

def solve():
    def cost(k,i):
        ai = a[i]
        if k == 0:
            return ai
        elif k == 1:
            if ai == 0:
                return 2
            return ai&1
        elif k == 2:
            return 1-(ai&1)
        elif k == 3:
            if ai == 0:
                return 2
            return ai&1
        else:
            return ai

    l = I()
    a = IR(l)
    dp = [[float("inf")]*5 for i in range(l)]
    for i in range(5):
        dp[0][i] = cost(i,0)
    for i in range(l-1):
        ni = i+1
        for j in range(5):
            for k in range(j,5):
                c = cost(k,ni)
                nd = dp[i][j]+c
                if nd < dp[ni][k]:
                    dp[ni][k] = nd
    print(min(dp[l-1]))
    return

#Solve
if __name__ == "__main__":
    solve()
