Алиса и Боб играют в игру. У них есть \(n\) шариков, \(i\)-й из них имеет цвет \(c_i\). Игроки ходят по очереди; сначала ходит Алиса, затем Боб, затем снова Алиса, затем опять Боб и так далее.
Во время своего хода игрок должен взять один из оставшихся шариков и убрать его из игры. Если шариков больше не осталось (все \(n\) шариков были взяты), игра заканчивается.
Очки Алисы в конце игры рассчитываются следующим образом:
- она получает \(1\) очко за каждый цвет \(x\), для которого она взяла хотя бы один шарик этого цвета;
- дополнительно она получает \(1\) очко за каждый цвет \(x\), для которого она взяла все шарики этого цвета (конечно, учитываются только цвета, присутствующие в игре).
Например, предположим, что есть \(5\) шариков, их цвета \([1, 3, 1, 3, 4]\), и игра проходит следующим образом: Алиса берет \(1\)-й шарик, затем Боб берет \(3\)-й шарик, затем Алиса берет \(5\)-й шарик, затем Боб берет \(2\)-й шарик, и, наконец, Алиса берет \(4\)-й шарик. Тогда Алиса получает \(4\) очка: \(3\) очка за наличие хотя бы одного шарика для цветов \(1\), \(3\) и \(4\), и \(1\) очко за наличие всех шариков цвета \(4\). Обратите внимание, что эта стратегия не обязательно является оптимальной для обоих игроков.
Алиса хочет максимизировать свои очки в конце игры. Боб хочет минимизировать их. Оба игрока играют оптимально (т. е. Алиса выбирает стратегию, которая позволяет ей получить как можно больше очков, а Боб выбирает стратегию, которая минимизирует количество очков, которые может получить Алиса).
Вычислите очки Алисы в конце игры.
Примечание
Во втором наборе входных данных примера цвета всех шариков различны, поэтому, независимо от того, как действуют игроки, Алиса получает \(4\) очка — у нее все шарики двух цветов и ни одного шарика третьего цвета.
В третьем наборе входных данных примера цвета всех шаров одинаковы, поэтому, независимо от того, как действуют игроки, Алиса получает \(1\) очко за то, что у нее хотя бы один (но не все) шарик цвета \(4\).