Добро пожаловать в армию, сынок. Джек служит рядовым и у него проблемы со строевой подготовкой. У него никак не получается делать как все: шаг левой, шаг правой, шаг левой, шаг правой и т.д. Заместо этого он запомнил некоторую последовательность действий и повторят ее по циклу. Например, он может запомнить «правой, левой, пропустить» и это значит, что первый шаг он сделает правой ногой, потом сделает шаг левой ногой, а потом и вовсе возьмет перерыв в то время как все остальные в строю делают очередной шаг. Затем он начнет повторять свои действия далее по циклу. Марширую таким образом он будет попадать в общий шаг лишь только в одной трети случаев.

Так как приближается парад Джек хочет модифицировать последовательность, которой он придерживается так, чтобы попадать в общий шаг с большей вероятностью. Так как Джек не любит напрягаться, он решает больше отдыхать во время марша — то есть модификация последовательности его шагов заключается в возможном добавлении пауз в нее (в любые позиции). Также он недавно обратил внимание, что ходить два раза подряд с одной ноги крайне неудобно. Поэтому в результате модификации во время парада он не должен шагать подряд с одной ноги.

Спасите рядового Джека. Задана текущая последовательность шагов. Вычислите какую наибольшую долю попаданий в общий шаг он может иметь после модификации ее.