题目描述
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
输入格式
见题面
输出格式
见题面