Вы когда-нибудь играли в Pudding Monsters? В этой задаче используется упрощенная одномерная модель этой игры.
Представьте себе бесконечную клетчатую полоску, клетки которой пронумерованы последовательно целыми числами. В некоторых клетках полоски стоят монстры, остальные клетки полоски пустые. Все монстры состоят из пудинга, поэтому, если два монстра стоят в соседних клетках полоски, то они склеиваются. Аналогично, если несколько монстров стоят подряд, то все они склеиваются в один блок монстров. Будем называть склеенных друг с другом монстров блоком монстров. Отдельно стоящий монстр, не склеенный ни с кем другим, также считается блоком.
За один ход игрок может взять любой блок монстров и движением руки швырнуть его влево или вправо. Выбранные монстры будут скользить до тех пор, пока не упрутся в какого-то другого монстра (или блок монстров).
Например, если на полоске стоят три монстра в клетках 1, 4 и 5. Тогда возможны только четыре хода: отправить монстра в клетке 1 в минус бесконечность, отправить блок монстров в клетках 4 и 5 в плюс бесконечность, швырнуть монстра 1 вправо (он остановится в клетке 3), швырнуть блок монстров в клетках 4 и 5 влево (они остановятся в клетках 2 и 3).
Некоторые клетки отмечены звездами. Это особенные клетки. Цель игры — сделать так, чтобы на максимально возможном количестве особенных клеток стояли монстры.
Вам заданы номера особенных клеток полоски, а также начальное положение всех монстров. Какое максимальное количество особых клеток можно занять монстрами?