Even Up Solitaire

Even Up Solitaire is played with a row of cards. Each card carries an integer from 1 to 100, and the cards are laid out from left to right.

On a move the player may remove two adjacent cards when the sum of their values is even. The gap closes: every card to the right of it shifts left, and the order of the remaining cards does not change. The game ends when all cards are gone, or when no adjacent pair sums to an even number. Removing every card wins. When that is impossible, the goal is to leave as few cards as possible.

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

The input is a single test case. The first line contains the number of cards $n$ ($1 \le n \le 100000$). The second line contains $n$ integers, the card values in left-to-right order. Each value is an integer from 1 to 100.

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