eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Even Up Solitaire

Even Up Solitaire

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

The 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 (1n100000) 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.

Пример

Входные данные #1
10
1 2 3 4 5 6 7 8 9 10
Выходные данные #1
10
Источник 2013 ACM-ICPC North American Qualification Contest