문제
음이 아닌 정수로 이루어진 길이 N의 배열 A = [
배열 A에서 인접한 두 수를 교환하는 시행을 원하는 만큼 할 수 있다.
이 때, 홀수와 짝수가 인접한 경우가 최대 1번 등장하도록 하는 시행의 최소 횟수를 구하여라.
단, 0 또한 짝수로 간주함에 유의하라.
예를 들어, 아래 그림과 같이 A = [4, 5, 1, 0]인 상황을 살펴보자.
이 경우, 마지막 두 원소를 교환하는 시행과 가운데 두 원소를 교환하는 시행을 차례로 수행하면
A가 [4, 0, 5, 1]이 되어 홀수와 짝수가 인접한 경우가 최대 1번 등장하도록 할 수 있다.
입력
첫 번째 줄에 정수 N이 주어진다.
두 번째 줄에 배열의 원소
[제약 조건]
• 1 ≤ N ≤ 1,000,000.
• 0 ≤
•
출력
첫 번째 줄에 답을 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | N ≤ 3. |
| #2 | 40점 | N ≤ 1,000. |
| #3 | 50점 | 추가 제약 조건 없음. |
예제1
입력
1
1
출력
0
예제2
입력
4
4510
출력
2
예제3
입력
4
1231
출력
1
태그
출처
KOI 1차 2022 중1/고1