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

def main():
    buf = input()
    L = int(buf)
    A = []
    for i in range(L):
        buf = input()
        A.append(int(buf))
    print(min(calc_move_count(A), calc_move_count(list(reversed(A)))))

def calc_move_count(A):
    stone_diff = []
    for i in A:
        if i == 0:
            stone_diff.append(1)
        elif i % 2 == 0:
            stone_diff.append(-1)
        else:
            stone_diff.append(0)
    no_left_sum = []
    for i in reversed(stone_diff):
        if not no_left_sum:
            no_left_sum.append(abs(i))
        else:
            no_left_sum.append(no_left_sum[-1] + abs(i))
    no_left_sum = list(reversed(no_left_sum))
    no_left_sum.append(0)
    move_left = [0]
    for i in A:
        if not move_left:
            move_left.append(i)
        else:
            move_left.append(move_left[-1] + i)
    move_right = []
    for i in reversed(A):
        if not move_right:
            move_right.append(i)
        else:
            move_right.append(move_right[-1] + i)
    move_right = list(reversed(move_right))
    move_right.append(0)
    dp = [[0, no_left_sum[0], 0, move_right[0]]]
    for i in range(len(A)):
        l = []
        l.append(min(move_left[i+1], dp[-1][0]+abs(stone_diff[i]+1)))
        l.append(min(move_left[i+1], l[0], dp[-1][1]+abs(stone_diff[i])-no_left_sum[i]) + no_left_sum[i+1])
        l.append(min(move_left[i+1], l[1]-no_left_sum[i+1], dp[-1][2]+abs(stone_diff[i]+1)))
        l.append(min(dp[-1][3], l[2] + move_right[i+1]))
        dp.append(l)
    return dp[-1][3]


if __name__ == '__main__':
    main()
