짝수 합 카드 놀이

카드를 한 줄로 늘어놓고 하는 짝수 합 카드 놀이가 있다. 각 카드에는 1 이상 100 이하의 정수가 하나씩 적혀 있고, 카드는 왼쪽에서 오른쪽으로 놓여 있다.

한 번의 차례에 이웃한 두 카드의 값의 합이 짝수이면 그 두 장을 없앨 수 있다. 두 장이 빠진 자리는 오른쪽에 있던 카드를 왼쪽으로 밀어서 메우고, 남은 카드의 순서는 바뀌지 않는다. 카드가 모두 없어지거나 합이 짝수인 이웃 쌍이 하나도 남지 않으면 놀이가 끝난다. 카드를 모두 없애면 이기고, 모두 없앨 수 없으면 남는 카드 수를 최소로 만드는 것이 목표다.

처음 카드 배열이 왼쪽에서 오른쪽 순서로 주어진다. 최선으로 없앴을 때 남는 카드의 최소 개수를 구하시오.

입력은 테스트 케이스 하나로 이루어진다. 첫째 줄에 카드의 개수 $n$이 주어진다 ($1 \le n \le 100000$). 둘째 줄에 카드에 적힌 값 $n$개가 왼쪽에서 오른쪽 순서로 주어진다. 각 값은 1 이상 100 이하의 정수다.

최선으로 없앴을 때 남는 카드의 최소 개수를 출력한다.