60046 피하자 Gold IV

문제

N개의 정수 수열이 주어진다. 인접 스왑을 통해 홀수와 짝수가 인접하는 경우가 최대 1번만 되도록 재배열할 때, 최소 스왑 횟수를 구하시오. (0은 짝수)

입력

첫째 줄에 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열이 주어진다.

출력

최소 스왑 횟수.