За решение этой задачи вы получите 5 баллов.

Манао изобрел новую операцию над строками, называемую сгибом. Каждый сгиб происходит между парой соседних символов в строке. В результате сгиба вторая часть строки оказывается над первой частью, только записывается она в противоположном направлении, при этом конец первой и начало второй части строки уравниваются. С помощью этой операции Манао превращает строку в структуру, которая имеет несколько уровней. Количество этих уровней на единицу больше количества сгибов в строке. Давайте рассмотрим несколько примеров.

Будем обозначать позиции сгибов символом '|'. Например, слово «ABRACADABRA», записанное как «AB|RACA|DAB|RA», обозначает, что было произведено три сгиба: первый — между левой парой букв 'B' и 'R'; второй — между буквами 'A' и 'D'; и третий, между правой парой 'B' и 'R'. Вот несколько примеров строк со сгибами:

"ABCDEF|GHIJK" |  "A|BCDEFGHIJK" |  "AB|RACA|DAB|RA" |  "X|XXXXX|X|X|XXXXXX"
               |                 |                   |       XXXXXX
    KJIHG      |   KJIHGFEDCB    |      AR           |       X
   ABCDEF      |            A    |     DAB           |       X
               |                 |     ACAR          |       XXXXX
               |                 |       AB          |           X

 K
IJ
HGFE
ABCD

Манао заметил, что согнутую строку можно рассматривать как несколько столбиков из символов. Например, в предыдущем примере согнутая строка представляет собой четыре столбика, которые можно прочитать как «AHI», «BGJK», «CF» и «DE» снизу вверх. Манао интересуется: какой самый высокий столбик из одинаковых букв он может получить, сгибая данную строку? Помогите ему ответить на этот вопрос. Учтите, что в столбике не должно быть пропусков, а также, что он должен начинаться на самом нижнем уровне (на том уровне, где записана самая левая часть строки). Например, в самом правом из четырех примеров выше, ни один из столбиков не устраивает Манао, так как каждый из них либо содержит пропуски, либо начинается выше первого уровня, либо и то и другое.