Навіть Угору Солітер
Гру "Even Up Solitaire" можна грати з колодою карт, кожна з яких має числове значення від 1 до 100. Карти викладаються в рядок зліва направо. На кожному кроці гравець може видалити дві сусідні карти, якщо сума їх значень є парною. Після видалення, проміжок "закривається" шляхом зміщення карт, що знаходяться праворуч від нього. Порядок решти карт залишається незмінним. Гра завершується, коли всі карти видалені або коли більше жодну карту не можна видалити. Гравець виграє, якщо всі карти видалені. Якщо це неможливо, гравець повинен намагатися мінімізувати кількість карт, що залишаться.
Вам надано початковий список карт, розташованих зліва направо. Визначте мінімальну кількість карт, що залишаться, якщо гравець діє оптимально.
Вхідні дані
Вхід складається з одного випадку. Перша строка містить ціле число n (1 ≤ n ≤ 100000), що вказує на кількість карт. Друга строка містить n цілих чисел, що представляють значення карт зліва направо. Кожне значення карти знаходиться в діапазоні від 1 до 100.
Вихідні дані
Виведіть мінімальну кількість карт, що залишаться, якщо гравець діє оптимально.