Андрей снова играет в свою любимую игру «World of Brawlcraft» вместо подготовки к олимпиаде

Андрей снова играет в свою любимую игру «World of Brawlcraft» вместо подготовки к олимпиаде.
На этот раз в качестве приза он получил строку s длины n. Пусть красота строки t — это
максимальное 1 6 k 6 n, что существует такое i, что:
1. 1 6 i 6 n − k + 1
2. ti 6 ti+1 6 . . . 6 ti+k−1
При сравнении символов сравниваются их номера в алфавите.
Иными словами, красота строки — длина максимальной неубывающей подстроки в s. Например,
красота строки «abbacbbc» равна 3, а красота строки «aaab» равна 4.
Однако, посчитать красоту строки — это слишком легко для Андрея, поэтому он решил усложнить задачу. Пусть циклический сдвиг строки s длины n на число k (1 6 k 6 n) — это строка
sk+1sk+2 . . . sns1s2 . . . sk. Например, циклический сдвиг строки «abbacbbc» на 5 равен «bbcabbac».
Задача Андрея такова: мальчик рассматривает всевозможные циклические сдвиги строки s, для
каждого из них вычисляет красоту, и находит циклический сдвиг с максимальной красотой. Андрей
уже смог решить эту задача и спросил у вас, чему равняется искомая максимальная красота строки.
Формат входных данных
Первая строка содержит одно целое число n (1 6 n 6 105
) — длину строки, полученную Андреем.
Далее записана строка, состоящая из n строчных латинских букв — строка, полученная Андреем.
Формат выходных данных
В качестве ответа выведите единственное число — максимальную красоту строки, которую можно получить при помощи циклического сдвига исходной строки s.

0

lifestyle

0