시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 16 13 10 83.333%

문제

aThe Even Up Solitaire can be played with a stack of cards each having a numerical value from 1 to 100. The cards are laid out from left to right in a row. At every step, the player is allowed to remove two adjacent cards if the sum of their values is even. The gap is then “closed” by shifting the cards to the right of the gap. The order of the remaining cards is not changed. The game stops when all cards are removed or when no more cards can be removed. The player wins when all cards are removed. If this is not possible, the player should try to minimize the number of cards remaining.

You are given the initial list of cards, in left-to-right order. Determine the minimum number of cards that remain if the player moves optimally.

입력

The input consists of one case. The first line contains an integer n (1 ≤ n ≤ 100000) giving the number of cards to follow. The second line contains n integers indicating the card values from left to right. Each card value is in the range 1 to 100.

출력

Print the minimum number of cards that remain if the player moves optimally.

예제 입력

10
1 2 3 4 5 6 7 8 9 10

예제 출력

10

예제 입력 2

10
1 3 3 4 2 4 1 3 7 1

예제 출력 2

2

힌트