피하자

시간 제한2초메모리 제한1024 MB

요약

인접한 두 수를 교환해 이웃한 쌍 중 홀짝이 다른 경우가 최대 한 번만 나오도록 만들 때 필요한 최소 교환 횟수를 구한다.

난이도: 보통10점 중 6점
유형: 그리디, 배열, 정렬
정답자: 아직 제출이 없습니다

문제

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

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

입력

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

두 번째 줄에 배열의 원소 A1, A2, · · · , AN이 사이에 공백을 두고 주어진다.

출력

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

제한

1 ≤ N ≤ 1 000 000.
0 ≤ Ai ≤ 2 × 109 (1 ≤ i ≤ N).
Ai는 정수이다.

예제3

예제 1
입력
```
1
1
```
예상 출력
```
0
```
예제 2
입력
```
4
4 5 1 0
```
예상 출력
```
2
```
예제 3
입력
```
4
1 2 3 1
```
예상 출력
```
1
```