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
import java.util.Scanner;

public class Main {
	int L;
	long[] Ai = null;

	long[] totalLeftAi1 = null;
	long[] totalLeftAi2 = null;
	long[] totalRightAi2 = null;
	
	private void prepare() {
		Scanner in = new Scanner(System.in);
		L = in.nextInt();
		Ai = new long[L+1];
		for (int i=1; i<=L; i++) {
			Ai[i] = in.nextInt();
		}
		in.close();

		long totalLeftAi = 0;
		totalLeftAi1 = new long[L+1];
		totalLeftAi2 = new long[L+1];
		totalLeftAi1[0] = 0;
		totalLeftAi2[0] = 0;
		for (int i=1; i<=L; i++) {
			totalLeftAi += Ai[i];
			if (Ai[i] < 1) {
				totalLeftAi1[i] = totalLeftAi1[i-1] + (1 - Ai[i]);
			} else {
				totalLeftAi1[i] = totalLeftAi1[i-1] + (Ai[i] + 1) % 2;
			}
			if (Ai[i] < 2) {
				totalLeftAi2[i] = totalLeftAi2[i-1] + (2 - Ai[i]);
			} else {
				totalLeftAi2[i] = totalLeftAi2[i-1] + (Ai[i] % 2);
			}
			if (totalLeftAi2[i] > totalLeftAi) {
				totalLeftAi2[i] = totalLeftAi;
			}
		}
		
		long totalRightAi = 0;
		totalRightAi2 = new long[L+2];
		totalRightAi2[L+1] = 0;
		
		for (int i=L; i>=1; i--) {
			totalRightAi += Ai[i];
			if (Ai[i] < 2) {
				totalRightAi2[i] = totalRightAi2[i+1] + (2 - Ai[i]);
			} else {
				totalRightAi2[i] = totalRightAi2[i+1] + (Ai[i] % 2);
			}
			if (totalRightAi2[i] > totalRightAi) {
				totalRightAi2[i] = totalRightAi;
			}
		}
		totalRightAi2[0] = totalRightAi2[1];
		
	}
	
	public long solve() {
		prepare();
		long min = Long.MAX_VALUE;

		long leftMin = Long.MAX_VALUE;
		
		long rightMins[] = new long[L+1];
		for (int right=L; right>=0; right--) {
			long rightScore = totalLeftAi1[right] + totalRightAi2[right+1];
			if (right==L) {
				rightMins[right] = rightScore;
			} else {
				if (rightMins[right+1] < rightScore) {
					rightMins[right] = rightMins[right+1];
				} else {
					rightMins[right] = rightScore;
				}
			}
		}
		
		for (int left=0; left<=L; left++) {
			long leftScore = totalLeftAi2[left] - totalLeftAi1[left];

			if (leftScore < leftMin) {
				leftMin = leftScore;
			} else {
				continue;
			}
			
			long rightScore = rightMins[left];
			
			if (min > leftScore + rightScore) {
				min = leftScore + rightScore;
			}
		}
		return min;
	}
	
	public static void main(String[] args) {
		Main main = new Main();
		System.out.println(main.solve());
	}
}