피하자

음이 아닌 정수로 이루어진 길이 $ N $의 배열 $ A = [A_1, A_2, \cdots, A_N] $가 있다. 배열 $ A $에서 인접한 두 수를 교환하는 시행을 원하는 만큼 할 수 있다. 이 때, 홀수와 짝수가 인접한 경우가 최대 1번 등장하도록 하는 시행의 최소 횟수를 구하여라. 단, $ 0 $ 또한 짝수로 간주함에 유의하라.

예를 들어, 아래 그림과 같이 $ A = [4, 5, 1, 0] $인 상황을 살펴보자. 이 경우, 마지막 두 원소를 교환하는 시행과 가운데 두 원소를 교환하는 시행을 차례로 수행하면 $ A $가 $ [4, 0, 5, 1] $이 되어 홀수와 짝수가 인접한 경우가 최대 1번 등장하도록 할 수 있다.

• $ 1 \le N \le 1\,000\,000 $.
• $ 0 \le A_i \le 2 \times 10^9 (1 \le i \le N) $.
• $A_i$는 정수이다.

1. (10점) $ N \le 3 $.
2. (40점) $ N \le 1\,000 $.
3. (50점) 추가 제약 조건 없음.

첫 번째 줄에 정수 $ N $이 주어진다.

두 번째 줄에 배열의 원소 $ A_1, A_2, \cdots, A_N $이 사이에 공백을 두고 주어진다.

첫 번째 줄에 답을 출력한다.