Пасьянс Even Up играется со стопкой карточек, на каждой из которых имеется число от 1 до 100. Карты выкладываются слева направо подряд. На каждом шагу игроку разрешается удалять две соседние карты, если сумма их значений четная. Затем разрыв «закрывается», карты вправо от зазора при этом сдвигаются влево. Порядок оставшихся карт не изменяется. Игра прекращается, когда все карты удалены или когда больше нечего удалять. Игрок выигрывает, когда все карты удаляются. Если это невозможно, игроку следует попытаться свести к минимуму количество оставшихся карт.
Вам дан первоначальный список карт в порядке слева направо. Определите минимальное количество оставшихся карт, если игрок действует оптимально.
Первая строка содержит количество карточек n, 1≤n≤100000. Вторая строка содержит n целых чисел - значения на карточках слева направо. Каждое значение в пределах от 1 до 100.
Выведите наименьшее количество оставшихся карточек.
| Sample input | Sample Output |
|---|---|
10 1 2 3 4 5 6 7 8 9 10 |
10 |
10 1 3 3 4 2 4 1 3 7 1 |
2 |