Even Up Solitaire
Игра "Even Up Solitaire" играется с колодой карт, где каждая карта имеет числовое значение от 1 до 100. Карты выкладываются в ряд слева направо. На каждом шаге игрок может удалить две соседние карты, если сумма их значений четная. После удаления, оставшиеся карты сдвигаются, заполняя образовавшийся промежуток, при этом их порядок сохраняется. Игра завершается, когда все карты удалены или когда больше нельзя удалить карты. Игрок выигрывает, если удается удалить все карты. Если это невозможно, игрок должен стремиться минимизировать количество оставшихся карт.
Вам дан начальный список карт в порядке слева направо. Определите минимальное количество карт, которое останется, если игрок будет действовать оптимально.
Входные данные
Входные данные состоят из одного тестового случая. Первая строка содержит целое число n (1 ≤ n ≤ 100000), обозначающее количество карт. Вторая строка содержит n целых чисел, представляющих значения карт слева направо. Каждое значение карты находится в диапазоне от 1 до 100.
Выходные данные
Выведите минимальное количество карт, которое останется, если игрок будет действовать оптимально.